Graph minors. IV. Tree-width and well-quasi-ordering

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

94 Scopus citations

Abstract

K. Wagner conjectured that if G1, G2, ... is any countable sequence of finite graphs, then there exist i, j with j > i ≥ 1 such that Gi is isomorphic to a minor of Gj. Kruskal proved this when G1, G2, ... are all trees. We prove a strengthening of Kruskal's result-Wagner's conjecture is true for all sequences in which G1 is planar. We hope to show in a future paper that Wagner's conjecture is true in general, and the results of this paper will be needed for that proof.

Original languageEnglish (US)
Pages (from-to)227-254
Number of pages28
JournalJournal of Combinatorial Theory, Series B
Volume48
Issue number2
DOIs
StatePublished - Apr 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Graph minors. IV. Tree-width and well-quasi-ordering'. Together they form a unique fingerprint.

Cite this