×

Graph minors. XX: Wagner’s conjecture. (English) Zbl 1061.05088

This paper is the culmination of a series investigating graph minors. In this work the authors prove Wagner’s conjecture: every infinite set of finite graphs contains one graph that is isomorphic to a minor of another. As a corollary: for every class of finite graphs closed under taking minors, there is a finite list of excluded minors characterizing that class.
The result is of fundamental importance in graph theory.

MSC:

05C83 Graph minors
05C65 Hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
Full Text: DOI

References:

[1] Robertson, N.; Seymour, P. D., Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B, 48, 227-254 (1990) · Zbl 0719.05032
[2] Robertson, N.; Seymour, P. D., Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 153-190 (1991) · Zbl 0764.05069
[3] Robertson, N.; Seymour, P. D., Graph minors. XVII. Taming a vortex, J. Combin. Theory Ser. B, 77, 162-210 (1999) · Zbl 1027.05088
[4] Robertson, N.; Seymour, P. D., Graph minors. XVIII. Tree-decompositions and well-quasi-ordering, J. Combin. Theory Ser. B, 89, 77-108 (2003) · Zbl 1023.05111
[5] Robertson, N.; Seymour, P. D., Graph minors. XIX. Well-quasi-ordering on a surface, J. Combin. Theory Ser. B, 90, 325-385 (2004) · Zbl 1035.05086
[6] K. Wagner, Graphentheorie, vol. 248/248a, B. J. Hochschultaschenbucher, Mannheim, 1970, p. 61.; K. Wagner, Graphentheorie, vol. 248/248a, B. J. Hochschultaschenbucher, Mannheim, 1970, p. 61. · Zbl 0195.54103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.