Two short proofs concerning tree-decompositions

被引：33

作者：

Bellenbaum, P ^{[1
]}

Diestel, R ^{[1
]}

机构：

[1] Univ Hamburg, Math Seminar, D-20146 Hamburg, Germany

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2002年 / 11卷 / 06期

关键词：

D O I：

10.1017/S0963548302005369

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give short proofs of the following two results: Thomas's theorem that every finite graph has a linked tree-decomposition of width no greater than its tree-width; and the 'tree-width duality theorem' of Seymour and Thomas, that the tree-width of a finite graph is exactly one less than the largest order of its brambles.

引用

页码：541 / 547

页数：7

共 10 条

[1]

BELLENBAUM P, 2000, THESIS U HAMBURG

[2] Highly connected sets and the excluded grid theorem [J].

Diestel, R ;

Jensen, TR ;

Gorbunov, KY ;

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (01) :61-73

[3]

Diestel R., 2000, GRAPH THEORY

[4] Branch-width and well-quasi-ordering in matroids and graphs [J].

Geelen, JF ;

Gerards, AMH ;

Whittle, G .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 84 (02) :270-290

[5]

GEELEN JF, 2000, EMBEDDING GRIDS SURF

[6]

Reed B., 1997, SURVEYS COMBINATORIC, V241, P87

[7] 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

[8] GRAPH SEARCHING AND A MIN MAX THEOREM FOR TREE-WIDTH [J].

SEYMOUR, PD ;

THOMAS, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 58 (01) :22-33

[9] A MENGER-LIKE PROPERTY OF TREE-WIDTH - THE FINITE CASE [J].

THOMAS, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :67-76

[10] A simpler proof of the excluded minor theorem for higher surfaces [J].

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 70 (02) :306-311

← 1 →