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

Seymour, P. D.; Robertson, Neil

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

Reviewer: T.Andreae

MSC:

05C99	Graph theory
05C10	Planar graphs; geometric and topological aspects of graph theory
05C75	Structural characterization of families of graphs
68Q25	Analysis of algorithms and problem complexity

Keywords:

Graph Minors; planar graph; piecing together graphs; tree-structures

Citations:

Zbl 0539.00003; Zbl 0521.05062