Metraipolis › archive › dc_ca9a43333499
Robertson–Seymour theorem — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-07T18:24:39.796Z
- SHA-256 of the archived text
22873ff189f41cf8a11ff1830f09c591ba4333ccdde743252f72a6857cd46053- Stable URL of this page
https://metraipolis.com/documento/dc_ca9a43333499
How to cite
Robertson–Seymour theorem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ca9a43333499 (Metraipolis archive dc_ca9a43333499, sha256 22873ff189f41cf8a11ff1830f09c591ba4333ccdde743252f72a6857cd46053)
BibTeX
@misc{dcca9a43333499,
title = {Robertson–Seymour theorem — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ca9a43333499; sha256 22873ff189f41cf8a11ff1830f09c591ba4333ccdde743252f72a6857cd46053},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under taking minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K 5 {\displaystyle K_{5}} or the complete bipartite graph K 3 , 3 {\displaystyle K_{3,3}} as minors. The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner, although Wagner said he never conjectured it. A weaker result for trees is implied by Kruskal's tree theorem, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal and S. Tarkowski.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Robertson–Seymour theorem» — https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem
Wikidata Q3527155: «mathematical theorem» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3527155
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem?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 1361823548, consultata il 2026-11-07T18:19:49.638Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 19321392c3c30f59a499660925c18754c5240dc2e83f812d0ec4d0391ae27ab2