# Talk:Cograph

WikiProject Mathematics (Rated Start-class, Mid-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Mid Importance
Field: Discrete mathematics

## 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.

↑Jump back a section

## 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_4$
• 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)

↑Jump back a section

## 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)

↑Jump back a section

## P4 notation

First, my substantive comment. I augmented the first characterization by explicitly including the notation P4. Since the article's introduction points out that the cographs are also known as the P4-free graphs, I figured it would add to the article's clarity if this P4 thing showed up somewhere below to tie things together.

Now a confession. I did it once and accidentally saved the page without having cretaed a comment to document the change in the history. So I immediately undid the change and re-implemented it, this time including the comment. That explains the 3 mods in such quick succession.—PaulTanenbaum (talk) 20:28, 9 July 2008 (UTC)

↑Jump back a section

## Proof for "Cographs are exaktly the graphs of clique-width at most 2"

Where can I find a proof for that. I searched for that in all the given References. —Preceding unsigned comment added by 141.20.6.79 (talk) 18:38, 9 March 2011 (UTC)

I added a source from the clique-width article. —David Eppstein (talk) 01:22, 10 March 2011 (UTC)
Thanks. And now I also found the proof that a graph who does not have the path of 3 edges as induced subgraph is a cograph: see Corneil, Lerchs, Stewart Burlingham: Complement reducible graphs (Discrete Applied Mathematics 3 (1981) pp. 167+168) and Seinsche: On a Property of the Class of n-Colorable Graphs (JOURNAL OF COMBINATORIAL THEORY (B) 16, pp. 191+192 (1974)). I remarked that in the article.Faust17 (talk)
↑Jump back a section