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

Robertson, Neil; Seymour, P. D.

J. Comb. Theory, Ser. B 92, No. 2, 325-357 (2004).

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.

Reviewer: Dan S. Archdeacon (Burlington)

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

Keywords:

graph; minor; surface embedding; well-quasi-ordering

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.