In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.
Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D*-graphs, hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices), and 2-parity graphs. They have a simple structural decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree, and used algorithmically to efficiently solve many problems such as finding the maximum clique that are hard on more general graph classes.
Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. The cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs.
Definition
Recursive construction
Any cograph may be constructed using the following rules: any single vertex graph is a cograph; if is a cograph, so is its complement graph ; if and are cographs, so is their disjoint union . The cographs may be defined as the graphs that can be constructed using these operations, starting from the single-vertex graphs. Alternatively, instead of using the complement operation, one can use the join operation, which consists of forming the disjoint union and then adding an edge between every pair of a vertex from and a vertex from .
Other characterizations
Several alternative characterizations of cographs can be given. Among them:
A cograph is a graph which does not contain the path P4 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. 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. A cograph is a comparability graph of a series-parallel partial order. A cograph is a permutation graph of a separable permutation. A cograph is a graph all of whose minimal chordal completions are trivially perfect graphs. A cograph is a hereditarily well-colored graph, a graph such that every greedy coloring of every induced subgraph uses an optimal number of colors. A graph is a cograph if and only if every vertex order of the graph is a perfect order, since having no P4 means that no obstruction to a perfect order will exist in any vertex order.
Cotrees
A cotree is a tree in which the internal nodes are labeled with the numbers 0 and 1. Every cotree T defines a cograph G having the leaves of T as vertices, and in which the subtree rooted at each node of T corresponds to the induced subgraph in G defined by the set of leaves descending from that node: A subtree consisting of a single leaf node corresponds to an induced subgraph with a single vertex. A subtree rooted at a node labeled 0 corresponds to the union of the subgraphs defined by the children of that node. A subtree rooted at a node labeled 1 corresponds to the join of the subgraphs defined by the children of that node; that is, we form the union and add an edge between every two vertices corresponding to leaves in different subtrees. Alternatively, the join of a set of graphs can be viewed as formed by complementing each graph, forming the union of the complements, and then complementing the resulting union. An equivalent way of describing the cograph formed from a cotree is that two vertices are connected by an edge if and only if the lowest common ancestor of the corresponding leaves is labeled by 1. Conversely, every cograph can be represented in this way by a cotree. If we require the labels on any root-leaf path of this tree to alternate between 0 and 1, this representation is unique.