Cograph

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 (Jung 1978), hereditary Dacey graphs (Sumner 1974), and 2-parity graphs (Burlet & Uhry 1984).

See, e.g., Brandstädt, Le & Spinrad (1999) for more detailed coverage of cographs, including the facts presented here.