##
**Some new results on the well-quasi-ordering of graphs.**
*(English)*
Zbl 0556.05058

Orders: description and roles, Proc. Conf. Ordered sets appl., l’Arbresle/France 1982, Ann. Discrete Math. 23, 343-354 (1984).

[For the entire collection see Zbl 0539.00003.]

This paper surveys the methods and results of the first five parts of the authors’ series of papers entitled ”Graph Minors”. (The first and the third of these outstanding papers have already appeared in print, see [J. Comb. Theory, Ser. B 35, 39-61 (1983; Zbl 0521.05062)] and [Graph minors III. Planar tree-width, ibid. 36, 49-64 (1984)].)

From the authors’ abstract: ” We have proved (1) that all graphs G not including a fixed planar graph H as a minor can be constructed by piecing together graphs on a bounded number of vertices in a tree-structure, and (2) by elaborating the Kruskal tree theorem that the class of graphs formed by piecing together graphs of bounded size in tree-structures is well-quasi-ordered. It follows from this that no infinite antichain of finite graphs can include even one planar graph and that there is a ”good” algorithm for testing the presence of a fixed planar graph as a minor.”

This paper surveys the methods and results of the first five parts of the authors’ series of papers entitled ”Graph Minors”. (The first and the third of these outstanding papers have already appeared in print, see [J. Comb. Theory, Ser. B 35, 39-61 (1983; Zbl 0521.05062)] and [Graph minors III. Planar tree-width, ibid. 36, 49-64 (1984)].)

From the authors’ abstract: ” We have proved (1) that all graphs G not including a fixed planar graph H as a minor can be constructed by piecing together graphs on a bounded number of vertices in a tree-structure, and (2) by elaborating the Kruskal tree theorem that the class of graphs formed by piecing together graphs of bounded size in tree-structures is well-quasi-ordered. It follows from this that no infinite antichain of finite graphs can include even one planar graph and that there is a ”good” algorithm for testing the presence of a fixed planar graph as a minor.”

Reviewer: T.Andreae