Graph minors. X. Obstructions to tree-decomposition

Neil Robertson; P. D. Seymour

doi:10.1016/0095-8956(91)90061-N

Graph minors. X. Obstructions to tree-decomposition

Neil Robertson, P. D. Seymour

Research output: Contribution to journal › Article › peer-review

504 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 language	English (US)
Pages (from-to)	153-190
Number of pages	38
Journal	Journal of Combinatorial Theory, Series B
Volume	52
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(91)90061-N
State	Published - Jul 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(91)90061-N

Cite this

@article{564f5aa5e3854fa18ab63dec3d35c298,

title = "Graph minors. X. Obstructions to tree-decomposition",

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.",

author = "Neil Robertson and Seymour, {P. D.}",

year = "1991",

month = jul,

doi = "10.1016/0095-8956(91)90061-N",

language = "English (US)",

volume = "52",

pages = "153--190",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Graph minors. X. Obstructions to tree-decomposition

AU - Robertson, Neil

AU - Seymour, P. D.

PY - 1991/7

Y1 - 1991/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0001227241&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001227241&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(91)90061-N

DO - 10.1016/0095-8956(91)90061-N

M3 - Article

AN - SCOPUS:0001227241

SN - 0095-8956

VL - 52

SP - 153

EP - 190

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Graph minors. X. Obstructions to tree-decomposition

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this