Cograph - Definition and Characterization

Definition and Characterization

Any cograph may be constructed using the following rules:

1. any single vertex graph is a cograph;
2. if is a cograph, so is its complement ;
3. if and are cographs, so is their disjoint union .

Several alternative characterizations of cographs can be given. Among them:

• A cograph is a graph which does not contain the path P₄ on 4 vertices (and hence of length 3) as an induced subgraph. That is, a graph is a cograph if and only if for any four vertices, if and are edges of the graph then at least one of or is also an edge (Corneil, Lerchs & Burlingham 1981).
• A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.
• A cograph is a graph in which every nontrivial induced subgraph has at least two vertices with the same neighbourhoods.
• A cograph is a graph in which every connected induced subgraph has a disconnected complement.
• A cograph is a graph all of whose connected induced subgraphs have diameter at most 2.
• A cograph is a graph in which every connected component is a distance-hereditary graph with diameter at most 2.
• A cograph is a graph with clique-width at most 2 (Courcelle & Olariu 2000).

All complete graphs, complete bipartite graphs, threshold graphs, and Turán graphs are cographs. Every cograph is distance-hereditary, a comparability graph, and perfect.

Cographs are the comparability graphs of series-parallel partial orders (Jung 1978).