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

Robertson, Neil; Seymour, P. D.

J. Comb. Theory, Ser. B 48, No. 2, 227-254 (1990).

[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.

Reviewer: J.Širáň (Bratislava)

MSC:

05C10

Planar graphs; geometric and topological aspects of graph theory

Keywords:

graph minor; tree-width; Wagner’s conjecture

Citations:

Zbl 0548.05025

References:

[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