GRAPH MINORS .10. OBSTRUCTIONS TO TREE-DECOMPOSITION

被引：423

作者：

ROBERTSON, N ^{[1
]}

SEYMOUR, PD ^{[1
]}

机构：

[1] BELLCORE,MORRISTOWN,NJ 07960

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1991年 / 52卷 / 02期

关键词：

D O I：

10.1016/0095-8956(91)90061-N

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. © 1991.

引用

页码：153 / 190

页数：38

共 8 条

[1]

[Anonymous], 1976, Matroid theory

[2]

[Anonymous], 1960, Math Nach, DOI [DOI 10.1002/MANA.19600220107, 10.1002/mana.19600220107.72]

[3] GRAPH MINORS .4. TREE-WIDTH AND WELL-QUASI-ORDERING [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (02) :227-254

[4] GRAPH MINORS .5. EXCLUDING A PLANAR GRAPH [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :92-114

[5] GRAPH MINORS .8. A KURATOWSKI THEOREM FOR GENERAL SURFACES [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (02) :255-288

[6]

ROBERTSON N, UNPUB GRAPH MINORS, V12

[7]

ROBERTSON N, UNPUB QUICKLY EXCLUD

[8]

ROBERTSON N, UNPUB GRAPH MINORS, V17

← 1 →