![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/640px-Turan_13-4.svg.png&w=640&q=50)
Cograph
Graph formed by complementation and disjoint union / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Cograph?
Summarize this article for a 10 year old
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/320px-Turan_13-4.svg.png)
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.