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

P. D. Seymour, Neil Robertson

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)343-354
Number of pages12
JournalNorth-Holland Mathematics Studies
Volume99
Issue numberC
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Some new results on the well-quasi-ordering of graphs'. Together they form a unique fingerprint.

  • Cite this