Metraipolis › archive › dc_4cea8e995c8f

Graph minor — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Graph_minor
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T17:34:02.648Z
SHA-256 of the archived text
61ecd9b5a78021361ada23b6c76585395617ee7900b26036d470576e8affc865
Stable URL of this page
https://metraipolis.com/documento/dc_4cea8e995c8f

How to cite

Graph minor — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Graph_minor (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_4cea8e995c8f (Metraipolis archive dc_4cea8e995c8f, sha256 61ecd9b5a78021361ada23b6c76585395617ee7900b26036d470576e8affc865)
BibTeX
@misc{dc4cea8e995c8f,
  title = {Graph minor — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Graph_minor},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_4cea8e995c8f; sha256 61ecd9b5a78021361ada23b6c76585395617ee7900b26036d470576e8affc865},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Graph_minor. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, an undirected graph H is called a minor of the undirected graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions. For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time. Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, and Hadwiger's conjecture relating the inability to color a graph to the existence of a large complete graph as a minor of it. Important variants of graph minors include the topological minors and immersion minors.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Graph minor» — https://en.wikipedia.org/wiki/Graph_minor
Wikidata Q905837 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q905837
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Graph_minor?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 1368857464, consultata il 2026-10-06T16:01:04.190Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 9e453f80b92a59f5f460e30793bdf82b99b15ddb332713dbed7884ccfe87d936