Cograph

Last updated January 02, 2024

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ 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.

Definition

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.^[4] 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₄ 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.^[4]
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.^[5]
A cograph is a comparability graph of a series-parallel partial order.^[1]
A cograph is a permutation graph of a separable permutation.^[6]
A cograph is a graph all of whose minimal chordal completions are trivially perfect graphs.^[7]
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.^[8]
A graph is a cograph if and only if every vertex order of the graph is a perfect order, since having no P₄ 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.^[4]

Computational properties

Cographs may be recognized in linear time, and a cotree representation constructed, using modular decomposition,^[9] partition refinement,^[10] LexBFS ,^[11] or split decomposition.^[12] Once a cotree representation has been constructed, many familiar graph problems may be solved via simple bottom-up calculations on the cotrees.

For instance, to find the maximum clique in a cograph, compute in bottom-up order the maximum clique in each subgraph represented by a subtree of the cotree. For a node labeled 0, the maximum clique is the maximum among the cliques computed for that node's children. For a node labeled 1, the maximum clique is the union of the cliques computed for that node's children, and has size equal to the sum of the children's clique sizes. Thus, by alternately maximizing and summing values stored at each node of the cotree, we may compute the maximum clique size, and by alternately maximizing and taking unions, we may construct the maximum clique itself. Similar bottom-up tree computations allow the maximum independent set, vertex coloring number, maximum clique cover, and Hamiltonicity (that is the existence of a Hamiltonian cycle) to be computed in linear time from a cotree representation of a cograph.^[4] Because cographs have bounded clique-width, Courcelle's theorem may be used to test any property in the monadic second-order logic of graphs (MSO₁) on cographs in linear time.^[13]

The problem of testing whether a given graph is k vertices away and/or t edges away from a cograph is fixed-parameter tractable.^[14] Deciding if a graph can be k-edge-deleted to a cograph can be solved in O^*(2.415^k) time,^[15] and k-edge-edited to a cograph in O^*(4.612^k).^[16] If the largest induced cograph subgraph of a graph can be found by deleting k vertices from the graph, it can be found in O^*(3.30^k) time.^[15]

Two cographs are isomorphic if and only if their cotrees (in the canonical form with no two adjacent vertices with the same label) are isomorphic. Because of this equivalence, one can determine in linear time whether two cographs are isomorphic, by constructing their cotrees and applying a linear time isomorphism test for labeled trees.^[4]

If H is an induced subgraph of a cograph G, then H is itself a cograph; the cotree for H may be formed by removing some of the leaves from the cotree for G and then suppressing nodes that have only one child. It follows from Kruskal's tree theorem that the relation of being an induced subgraph is a well-quasi-ordering on the cographs.^[17] Thus, if a subfamily of the cographs (such as the planar cographs) is closed under induced subgraph operations then it has a finite number of forbidden induced subgraphs. Computationally, this means that testing membership in such a subfamily may be performed in linear time, by using a bottom-up computation on the cotree of a given graph to test whether it contains any of these forbidden subgraphs. However, when the sizes of two cographs are both variable, testing whether one of them is an induced subgraph of the other is NP-complete.^[18]

Cographs play a key role in algorithms for recognizing read-once functions.^[19]

Some counting problems also become tractable when the input is restricted to be a cograph. For instance, there are polynomial-time algorithms to count the number of cliques or the number of maximum cliques in a cograph^[4].

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, ... (sequence A000669 in the OEIS )

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 $K n$ is a cograph, with a cotree consisting of a single 1-node and $n$ leaves. Similarly, every complete bipartite graph $K a, b$ is a cograph. Its cotree is rooted at a 1-node which has two 0-node children, one with $a$ leaf children and one with $b$ 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. ^[20]

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.^[21]

The fact that cographs are P₄-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.^[20]

Related Research Articles

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In the mathematical field of graph theory, the complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$ . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

In graph theory, a path decomposition of a graph $G$ is, informally, a representation of $G$ as a "thickened" path graph, and the pathwidth of $G$ is a number that measures how much the path was thickened to form $G$ . More formally, a path-decomposition is a sequence of subsets of vertices of $G$ such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex $v$ in a graph is a vertex that is connected to $v$ by an edge. The neighbourhood of a vertex $v$ in a graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$ , i.e., the graph composed of the vertices adjacent to $v$ and all edges connecting vertices adjacent to $v$ .

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979), where they called these graphs "polar graphs".

<span class="mw-page-title-main">Threshold graph</span> Graph formed by adding isolated or universal vertices

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

Addition of a single isolated vertex to the graph.
Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

In graph theory, the clique-width of a graph $G$ is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct $G$ by means of the following 4 operations :

Creation of a new vertex $v$ with label $i$ (denoted by $i (v)$ )
Disjoint union of two labeled graphs $G$ and $H$ (denoted by $)$
Joining by an edge every vertex labeled $i$ to every vertex labeled $j$ (denoted by $η (i, j)$ ), where $i \neq j$
Renaming label $i$ to label $j$ (denoted by $ρ (i, j)$ )

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum $k$ for which a clique cover exists is called the clique cover number of the given graph.

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for its vertices. That is, for these graphs, the chromatic number and Grundy number are equal.

References

Berge, C.; Duchet, P. (1984), "Strongly perfect graphs", Topics on Perfect Graphs, North-Holland Mathematics Studies, vol. 88, Amsterdam: North-Holland, pp. 57–61, doi:10.1016/S0304-0208(08)72922-0, MR 0778749 .
Bose, Prosenjit; Buss, Jonathan; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters , 65 (5): 277–283, doi:10.1016/S0020-0190(97)00209-3, MR 1620935 .
Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6 .
Burlet, M.; Uhry, J. P. (1984), "Parity Graphs", Topics on Perfect Graphs, Annals of Discrete Mathematics, vol. 21, pp. 253–277.
Bretscher, A.; Corneil, D. G.; Habib, M.; Paul, C. (2008), "A simple Linear Time LexBFS Cograph Recognition Algorithm", SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016 , doi:10.1137/060664690 .
Cai, L. (1996), "Fixed-parameter tractability of graph modification problems for hereditary properties", Information Processing Letters , 58 (4): 171–176, doi:10.1016/0020-0190(96)00050-6 .
Christen, Claude A.; Selkow, Stanley M. (1979), "Some perfect coloring properties of graphs", Journal of Combinatorial Theory , Series B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, MR 0539075 .
Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics , 3 (3): 163–174, doi:10.1016/0166-218X(81)90013-5, MR 0619603 .
Corneil, D. G.; Perl, Y.; Stewart, L. K. (1985), "A linear recognition algorithm for cographs", SIAM Journal on Computing , 14 (4): 926–934, doi:10.1137/0214065, MR 0807891 .
Courcelle, B.; Makowsky, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs of bounded clique-width", Theory of Computing Systems, 33 (2): 125–150, doi:10.1007/s002249910009, MR 1739644, S2CID 15402031, Zbl 1009.68102 .
Courcelle, B.; Olariu, S. (2000), "Upper bounds to the clique width of graphs", Discrete Applied Mathematics , 101 (1–3): 77–144, doi: 10.1016/S0166-218X(99)00184-5 , MR 1743732 .
Damaschke, Peter (1990), "Induced subgraphs and well-quasi-ordering", Journal of Graph Theory , 14 (4): 427–435, doi:10.1002/jgt.3190140406, MR 1067237 .
Damaschke, Peter (1991), "Induced subraph isomorphism for cographs is NP-complete", in Möhring, Rolf H. (ed.), Graph-Theoretic Concepts in Computer Science: 16th International Workshop WG '90 Berlin, Germany, June 20–22, 1990, Proceedings, Lecture Notes in Computer Science, vol. 484, Springer-Verlag, pp. 72–78, doi:10.1007/3-540-53832-1_32 .
Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics, 160 (6): 708–733, arXiv: 0810.1823 , doi:10.1016/j.dam.2011.05.007, MR 2901084, S2CID 6528410 .
Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 .

Habib, Michel; Paul, Christophe (2005), "A simple linear time algorithm for cograph recognition" (PDF), Discrete Applied Mathematics , 145 (2): 183–197, doi:10.1016/j.dam.2004.01.011, MR 2113140 .
Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory , Series B, 24 (2): 125–133, doi: 10.1016/0095-8956(78)90013-8 , MR 0491356 .
Lerchs, H. (1971), On cliques and kernels, Tech. Report, Dept. of Comp. Sci., Univ. of Toronto.
Liu, Yunlong Liu; Wang, Jianxin; Guo, Jiong; Chen, Jianer (2012), "Complexity and parameterized algorithms for Cograph Editing", Theoretical Computer Science, 461: 45–54, doi: 10.1016/j.tcs.2011.11.040 .
Nastos, James; Gao, Yong (2010), "A novel branching strategy for parameterized graph modification problems", in Wu, Weili; Daescu, Ovidiu (eds.), Combinatorial Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18–20, 2010, Proceedings, Part II, Lecture Notes in Computer Science, vol. 6509, Springer, pp. 332–346, arXiv: 1006.3020 , doi:10.1007/978-3-642-17461-2_27
Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", 4th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1995), Discrete Applied Mathematics , 79 (1–3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR 1478250 .
Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory , Series B, 16 (2): 191–193, doi: 10.1016/0095-8956(74)90063-X , MR 0337679 .
Sumner, D. P. (1974), "Dacey graphs", Journal of the Australian Mathematical Society, 18 (4): 492–502, doi: 10.1017/S1446788700029232 , MR 0382082 .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FOOTNOTEJung1978-1] 1 2 Jung (1978).

[FOOTNOTESumner1974-2] Sumner (1974).

[FOOTNOTEBurletUhry1984-3] Burlet & Uhry (1984).

[FOOTNOTECorneilLerchsStewart_Burlingham1981-4] 1 2 3 4 5 6 Corneil, Lerchs & Stewart Burlingham (1981).

[FOOTNOTECourcelleOlariu2000-5] Courcelle & Olariu (2000).

[FOOTNOTEBoseBussLubiw1998-6] Bose, Buss & Lubiw (1998).

[FOOTNOTEParraScheffler1997-7] Parra & Scheffler (1997).

[FOOTNOTEChristenSelkow1979-8] Christen & Selkow (1979).

[FOOTNOTECorneilPerlStewart1985-9] Corneil, Perl & Stewart (1985).

[FOOTNOTEHabibPaul2005-10] Habib & Paul (2005).

[FOOTNOTEBretscherCorneilHabibPaul2008-11] Bretscher et al. (2008).

[FOOTNOTEGioanPaul2012-12] Gioan & Paul (2012).

[FOOTNOTECourcelleMakowskyRotics2000-13] Courcelle, Makowsky & Rotics (2000).

[FOOTNOTECai1996-14] Cai (1996).

[FOOTNOTENastosGao2010-15] 1 2 Nastos & Gao (2010).

[FOOTNOTELiuWangGuoChen2012-16] Liu et al. (2012).

[FOOTNOTEDamaschke1990-17] Damaschke (1990).

[FOOTNOTEDamaschke1991-18] Damaschke (1991).

[FOOTNOTEGolumbicGurvich2011-19] Golumbic & Gurvich (2011).

[FOOTNOTEBrandstädtLeSpinrad1999-20] 1 2 Brandstädt, Le & Spinrad (1999).

[FOOTNOTEBergeDuchet1984-21] Berge & Duchet (1984).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]