Cograph

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).

[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.

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: 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.

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.

[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.

It follows from Kruskal's tree theorem that the relation of being an induced subgraph is a well-quasi-ordering on the cographs.

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

Every complete graph Kn is a cograph, with a cotree consisting of a single 1-node and n leaves.

[20] 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.

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.