Graph minors. I. Excluding a forest

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticle

332 Scopus citations

Abstract

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG1,...,Gr each of which has at mostk + 1 vertices, by identifying some vertices ofGi pairwise with some ofGi+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width{approximately but not actually equal to}k. This, together with results of other papers, yields a "good" algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.

Original languageEnglish (US)
Pages (from-to)39-61
Number of pages23
JournalJournal of Combinatorial Theory, Series B
Volume35
Issue number1
DOIs
StatePublished - Aug 1983
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. I. Excluding a forest'. Together they form a unique fingerprint.

Cite this