Graph minors. X. Obstructions to tree-decomposition

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticle

381 Scopus citations

Abstract

Roughly, a graph has small "tree-width" if it can be constructed by piecing small graphs together in a tree structure. Here we study the obstructions to the existence of such a tree structure. We find, for instance: 1. (i) a minimax formula relating tree-width with the largest such obstructions 2. (ii) an association between such obstructions and large grid minors of the graph 3. (iii) a "tree-decomposition" of the graph into pieces corresponding with the obstructions. These results will be of use in later papers.

Original languageEnglish (US)
Pages (from-to)153-190
Number of pages38
JournalJournal of Combinatorial Theory, Series B
Volume52
Issue number2
DOIs
StatePublished - Jan 1 1991
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. X. Obstructions to tree-decomposition'. Together they form a unique fingerprint.

  • Cite this