The Menger-like property of the three-width of infinite graphs (Q1121910)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Menger-like property of the three-width of infinite graphs |
scientific article |
Statements
The Menger-like property of the three-width of infinite graphs (English)
0 references
1991
0 references
The tree-width of a (possibly infinite) graph G is the minimum n such that G may be decomposed into a ``tree-structure'' of pieces each with at most \(n+1\) vertices. We prove that if G has tree-width n, then G can be decomposed in such a way that for every \(k\geq 0\) and any two pieces P and Q of this ``tree-structure'' either there are k disjoint paths between P and Q, or there is third piece R between P and Q with at most k-1 vertices. Our proof makes use of a finite version of this result proved by the second author and a compactness argument.
0 references
connectivity
0 references
tree-width
0 references
graph
0 references
compactness
0 references