Graph minors. IV: Tree-width and well-quasi-ordering (Q2639869): Difference between revisions

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