Excluding infinite minors

Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Let κ be an infinite cardinal, and let H be either a complete graph with κ vertices, or a tree in which every vertex has valency κ. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H? These four questions are answered for each infinite cardinal κ. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.

Original languageEnglish (US)
Pages (from-to)303-319
Number of pages17
JournalDiscrete Mathematics
Volume95
Issue number1-3
DOIs
StatePublished - Dec 3 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Excluding infinite minors'. Together they form a unique fingerprint.

Cite this