Graph formed by complementation and disjoint union
The Turán graph T(13,4), an example of a cograph
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 Jung (1978), Lerchs (1971), Seinsche (1974), and Sumner (1974). They have also been called D*-graphs,[1]hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices),[2] and 2-parity graphs.[3]
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.
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...
self-complementary family of graphs: the complement of any cograph is another different cograph. For cographs of more than one vertex, exactly one graph in each...
special case of cographs, split graphs, and trivially perfect graphs. A graph is a threshold graph if and only if it is both a cograph and a split graph...
describe a cograph, in which each cograph vertex is a leaf of the tree, each internal node of the tree is labeled with 0 or 1, and two cograph vertices...
graph with girth 5 (Montassier & Ochem 2015). The subchromatic number of a cograph can be computed in polynomial time (Fiala et al. 2003). For every fixed...
and their complement graphs, the cluster graphs, are special cases of cographs, and can be recognized in polynomial time even when the partition is not...
equivalence classes for this relation. Every cluster graph is a block graph, a cograph, and a claw-free graph. Every maximal independent set in a cluster graph...
graphs of bounded clique-width. These include, among other graphs, the cographs and distance-hereditary graphs, which are both also classes of perfect...
(that is, graphs having no independent set of more than two vertices), cographs and interval graphs, and even for trees. For complements of trees, the...
gene and species trees based on event-relations (orthology, paralogy) Cograph-Editing and Triple-Inference Hellmuth PartitionFinder Combined selection...
Quasi-threshold graphs are a subclass of Ptolemaic graphs that are both chordal and cographs. Block graphs are another subclass of Ptolemaic graphs in which every two...
graph classes including AT-free graphs, claw-free AT-free graphs, and cographs. The minimum chordal completion was one of twelve computational problems...
graphs include triangle-free graphs, bipartite graphs, and interval graphs. Cographs can be characterized as graphs in which every maximal clique intersects...
whole graph. If only the twin operations are used, the result is a cograph. The cographs are the comparability graphs of series-parallel partial orders and...
permutation graphs (characterized by Spinrad, Brandstädt & Stewart 1987) and the cographs. Brandstädt, Le & Spinrad (1999), p.191. Brandstädt, Le & Spinrad (1999)...
chordal graphs and graphs of bounded clique-width. The latter class includes cographs and graphs of bounded tree-width, such as outerplanar graphs. The deletion-contraction...
deleting some one vertex. For example, an apex-cograph is a graph G that has a vertex v such that G―v is a cograph. Polyhedral pyramid, a 4-dimensional polytope...
Global Information