TY - JOUR

T1 - Some new results on the well-quasi-ordering of graphs

AU - Seymour, P. D.

AU - Robertson, Neil

N1 - Funding Information:
Partially supported by National Science Foundation grant number MCS 8103440 .
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1984/1/1

Y1 - 1984/1/1

N2 - It has been conjectured by K. WAGNER that finite graphs are well-quasi-ordered by minor inclusion, i.e. being isomorphic to a contraction of a subgraph. A method is reported on here that shows promise of settling this conjecture. 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.

AB - It has been conjectured by K. WAGNER that finite graphs are well-quasi-ordered by minor inclusion, i.e. being isomorphic to a contraction of a subgraph. A method is reported on here that shows promise of settling this conjecture. 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.

UR - http://www.scopus.com/inward/record.url?scp=77956925213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956925213&partnerID=8YFLogxK

U2 - 10.1016/S0304-0208(08)73830-1

DO - 10.1016/S0304-0208(08)73830-1

M3 - Article

AN - SCOPUS:77956925213

VL - 99

SP - 343

EP - 354

JO - North-Holland Mathematics Studies

JF - North-Holland Mathematics Studies

SN - 0304-0208

IS - C

ER -