A MENGER-LIKE PROPERTY OF TREE-WIDTH - THE FINITE CASE

被引：33

作者：

THOMAS, R

机构：

[1] UNIV READING,READING RG6 2AH,BERKS,ENGLAND

[2] CHARLES UNIV,DEPT MATH ANAL,CS-18600 PRAGUE 8,CZECHOSLOVAKIA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1990年 / 48卷 / 01期

关键词：

D O I：

10.1016/0095-8956(90)90130-R

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The notion of tree-width was introduced by Robertson and Symour. A graph has tree-width ≦ w if it admits a tree-decomposition of tree-width ≦ w. We prove here that if G is finite and has tree-width ≦ w then it admits a tree-decomposition of tree-width ≦ w which satisfies a certain Menger-like condition. This result will be used in a future paper on well-quasi-ordering infinite graphs of bounded tree-width. © 1990.

引用

页码：67 / 76

页数：10