Graph minors. IV: Tree-width and well-quasi-ordering. (English) Zbl 0719.05032

[Part III, cf. ibid. 36, 49-64 (1984; Zbl 0548.05025.]
The famous conjecture of K. Wagner says that if \(G_ 1,G_ 2,..\). is any countably infinite sequence of finite graphs, then there exist \(i,j,j>i\geq 1\) such that \(G_ i\) is isomorphic to a minor of \(G_ j\). By a result of Kruskal, this is true if all the \(G_ i's\) are trees. The authors extend Kruskal’s theorem to all sequences in which the first member \(G_ 1\) is planar. This is one of the steps towards establishing the truth of Wagner’s conjecture in general.


05C10 Planar graphs; geometric and topological aspects of graph theory


Zbl 0548.05025
Full Text: DOI


[1] Archdeacon, D, A Kuratowski theorem for the projective plane, () · Zbl 0464.05028
[2] Glover, H; Huneke, P; Wang, C.S, 103 graphs that are irreducible for the projective plane, J. combin. theory ser. B, 27, 332-370, (1979) · Zbl 0352.05027
[3] Higman, G, Ordering by divisibility in abstract algebras, (), 326-336 · Zbl 0047.03402
[4] Jenkyns, T.A; Nash-Williams, C.St.J.A, Counterexamples in the theory of well-quasi-ordered sets, (), 87-91 · Zbl 0197.28901
[5] Kruskal, J, Well-quasi-ordering, the tree theorem, and Vázsonyi’s conjecture, Trans. amer. math. soc., 95, 210-225, (1960) · Zbl 0158.27002
[6] Mader, W, Wohlquasiordnete klassen endlicher graphen, J. combin. theory ser. B, 12, 105-122, (1972) · Zbl 0212.29404
[7] Nash-Williams, C.St.J.A, On well-quasi-ordering finite trees, (), 833-835 · Zbl 0122.25001
[8] Robertson, N; Seymour, P.D, Graph minors. II. algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[9] Robertson, N; Seymour, P.D, Graph minors. III, planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[10] Robertson, N; Seymour, P.D, Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[11] Robertson, N; Seymour, P.D, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. combin. theory ser. B, 48, 255-288, (1990) · Zbl 0719.05033
[12] Simpson, S.G, Non-provability of certain combinatorial properties of finite trees, (), 87-117
[13] {\scR. Thomas}, A Menger-like property of tree-width. The finite case, J. Combin. Theory Ser. B, to appear. · Zbl 0636.05022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.