Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Cograph
Summary
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.
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 .
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.