Talk:Cograph

From Wikipedia, the free encyclopedia

[edit] Too technical

I'm not sure it's needed to explain every technical thing in the Wikipedia in a language that anyone would understand. For instance, the explanation for this still-simple article seams quite absurd (Mariano 16:46, 25 August 2005 (UTC)):

1. Can be constructed from (1) isolated vertices by (2) complement and (3) disjoint union. This means that:

1. A group of isolated vertices is a Cograph
2. if G is a Cograph, then changing the edges so that x will be adjacent to y if it was not adjacent of it in the original, but x will not be adjacent to y if it was in the original.
3. if G and J are a Cograph, then the graph of putting together G and J without new edges is also a Cograph

And, tat any Cograph can be constructed following this 3 rules.

2. Can be (1) decomposed by (2) isolated vertex elimination and complement. G ∪ {x} (G union an element x) is also a Cograph This means that we can play "She loves me, she loves me not" with the graph, taking vertices that are not connected to any other vertex, or complement the graph, and we will end up with an empty graph.

3. It contains no induced [Glossary_of_graph_theory#Path|path]] of length at least 4. A P4 of a graph is a path of 4 distinct vertices a, b, c and d, with a connected to b, b connected to c, and c connected to d, such that to go from a to b I have no shortcut. Therefore, if our graph G has a P4, then is not a Cograph, and if it doesn't have it, it is a Cograph.

4. The maximum distance between two vertices in the same connected component is at most 2. If there is a path from a to b, then the shortest path between them includes one more vertex, or none at all.

5. Has at least one pair of false or true twins (that have the same opened or closed neighbourhood). This means that if G is a Cograph, then there must exist vertices a and b such that all the neighbours of a are also neighbours of b. Bear in mind that it doesn't matter if a and b are neighbours.

[edit] Cleaning

I tried to simplify the entry. I stressed the constructive definition, which is not so difficult to handle and gave some of the possible other ones as characterizations (formally, we may not have more than one definition). I removed the characterization by twins which has mainly a technical interest, but I kept:

1. the characterization by forbidden P₄
   • for historical reasons (it is one of the independent introductions of the class)
   • as it is quite simple although not obviously related to the main definition
2. the characterization by the diameters of the connected subgraphs
   • as it is clearly related to the previous one
   • as it enhances the intuition of what a cograph looks like
3. the characterization by clique-independent set intersection
   • as it is one the strong properties of cographs, even stronger than the property to be trivially perfect. It is the fundamental reason of the low complexity of coloring problems in this class.

I also have added some references.

pom 14:50, 14 November 2005 (UTC)

[edit] Category

As noticed by D. Eppstein, Cographs are not a parametrized family hence should not belong to Category:Graph. pom 23:56, 5 October 2006 (UTC)