Cograph

T(13,4) is a cograph In graph theory, a cograph, or complement-reducible graph, or P 4 -free graph, is a graph that can be generated from the single-vertex graph K 1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K 1 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 a maximum clique that are hard on more general graph classes. Special types of cograph include complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. Cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs.

T(13,4) is a cograph]] In graph theory, a cograph, or complement-reducible graph, or P 4 -free graph, is a graph that can be generated from the single-vertex graph K 1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K 1 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 a maximum clique that are hard on more general graph classes. Special types of cograph include complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. Cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs. ===Recursive construction=== Any cograph may be constructed using the following rules: any single-vertex graph is a cograph; if G is a cograph, so is its complement, \overline{G} ; if G and H are cographs, so is their disjoint union, G\cup H . 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 G\cup H and then adding an edge between every pair of a vertex from G and a vertex from H . ===Other characterizations=== Several alternative characterizations of cographs can be given. Among them: A cograph is a graph which does not contain the path P 4 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 v_1,v_2,v_3,v_4 , if \{v_1,v_2\},\{v_2,v_3\} and \{v_3,v_4\} are edges of the graph then at least one of \{v_1,v_3\},\{v_1,v_4\} or \{v_2,v_4\} 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 nontrivial 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 P 4 means that no obstruction to a perfect order will exist in any vertex order. ==Enumeration== The number of connected cographs with n vertices, for n = 1, 2, 3, ..., is: 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... For n > 1 there are the same number of disconnected cographs, because for every cograph exactly one of it or its complement graph is connected. ==Related graph families== ===Subclasses=== Every complete graph is a cograph, with a cotree consisting of a single 1-node and leaves. Similarly, every complete bipartite graph is a cograph. Its cotree is rooted at a 1-node which has two 0-node children, one with leaf children and one with leaf children. A Turán graph may be formed by the join of a family of equal-sized independent sets; thus, it also is a cograph, with a cotree rooted at a 1-node that has a child 0-node for each independent set. Every threshold graph is also a cograph. A threshold graph may be formed by repeatedly adding one vertex, either connected to all previous vertices or to none of them; each such operation is one of the disjoint union or join operations by which a cotree may be formed. ===Superclasses=== The characterization of cographs by the property that every clique and maximal independent set have a nonempty intersection is a stronger version of the defining property of strongly perfect graphs, in which there every induced subgraph contains an independent set that intersects all maximal cliques. In a cograph, every maximal independent set intersects all maximal cliques. Thus, every cograph is strongly perfect. The fact that cographs are P 4 -free implies that they are perfectly orderable. In fact, every vertex order of a cograph is a perfect order which further implies that max clique finding and min colouring can be found in linear time with any greedy colouring and without the need for a cotree decomposition. Every cograph is a distance-hereditary graph, meaning that every induced path in a cograph is a shortest path. The cographs may be characterized among the distance-hereditary graphs as having diameter at most two in each connected component. Every cograph is also a comparability graph of a series-parallel partial order, obtained by replacing the disjoint union and join operations by which the cograph was constructed by disjoint union and ordinal sum operations on partial orders. Because strongly perfect graphs, perfectly orderable graphs, distance-hereditary graphs, and comparability graphs are all perfect graphs, cographs are also perfect. ==Notes==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368905708 under CC BY-SA 4.0; modifications have been made.