cograph
Sign in to saveAlso known as complement-reducible graph, P4-free graph
thumb|The Turán graph T(13,4) is a cograph 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 K''1 and is closed under complementation and disjoint union.
Wikidata facts
- Image
- Complete bipartite graph K3,2.svg
Show 1 more fact
- Stack Exchange tag
- cstheory.stackexchange.com/tags/cograph
Sources (2)
via Wikidata · CC0
~11 min read
Article
12 sectionsContents
- Definition
- Recursive construction
- Other characterizations
- Cotrees
- Computational properties
- Enumeration
- Related graph families
- Subclasses
- Superclasses
- Notes
- References
- External links
thumb|The Turán graph T(13,4) is a cograph 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 a maximum clique that are hard on more general graph classes.