Metraipolis › archive › dc_e2042340c142
Cograph — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Cograph
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-31T09:55:54.354Z
- SHA-256 of the archived text
32cf3a7651425c052a79a7a89da5a5910691aa6e3e2fa4906a50f0ec49b06dd7- Stable URL of this page
https://metraipolis.com/documento/dc_e2042340c142
How to cite
Cograph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Cograph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e2042340c142 (Metraipolis archive dc_e2042340c142, sha256 32cf3a7651425c052a79a7a89da5a5910691aa6e3e2fa4906a50f0ec49b06dd7)
BibTeX
@misc{dce2042340c142,
title = {Cograph — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Cograph},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e2042340c142; sha256 32cf3a7651425c052a79a7a89da5a5910691aa6e3e2fa4906a50f0ec49b06dd7},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Cograph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 Jung (1978), Lerchs (1971), Seinsche (1974), and Sumner (1974). 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. Special types of cograph include complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. Cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»). Fonte: Wikipedia in inglese, voce «Cograph» — https://en.wikipedia.org/wiki/Cograph Wikidata Q5141281: «a type of graph, formed recursively by complementation and disjoint union operations» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5141281 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Cograph?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1368905708, consultata il 2026-10-31T09:41:21.892Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: bc648555fe2a297f45480d9e5b904fe323e0c5a3f24f3ab9784bb9e661708474