Talk:Cograph

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)):[reply]

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

A group of isolated vertices is a Cograph
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.
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.

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:

the characterization by forbidden $P_{4}$ $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
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
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)[reply]

P₄ notation

First, my substantive comment. I augmented the first characterization by explicitly including the notation P₄. Since the article's introduction points out that the cographs are also known as the P₄-free graphs, I figured it would add to the article's clarity if this P₄ 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)[reply]

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)[reply]

I added a source from the clique-width article. —David Eppstein (talk) 01:22, 10 March 2011 (UTC)[reply]

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)

Union of graphs undefined

The concept of (disjoint) union is generally defined only for sets, which graphs are not because they are pairs of sets.

If an abuse of notation is being adopted, it should be clarified somewhere. — Preceding unsigned comment added by 213.46.252.136 (talk) 10:41, 12 January 2015 (UTC)[reply]

The disjoint union of graphs is standard and well defined; see Graph operations. It is a different operation than the disjoint union of sets, because it has arguments of a different type (graphs not sets). It is not an abuse of notation. —David Eppstein (talk) 17:12, 12 January 2015 (UTC)[reply]

Assessment comment

The comment(s) below were originally left at Talk:Cograph/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Too high a ratio of lists to text. —David Eppstein 03:23, 14 May 2007 (UTC)[reply]

Last edited at 03:23, 14 May 2007 (UTC). Substituted at 01:53, 5 May 2016 (UTC)