The Menger-like property of the three-width of infinite graphs
type: Item
instance of: scholarly article
title: The Menger-like property of the three-width of infinite graphs
zbMATH Open document ID: 0675.05046
author: Robin Thomas
author: Igor Kriz
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4105001
zbMATH Keywords: connectivity
zbMATH Keywords: tree-width
zbMATH Keywords: graph
zbMATH Keywords: compactness
MaRDI profile type: Publication
cites work: Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen
cites work: Q4064160
cites work: Clique-sums, tree-decompositions and compactness
cites work: Q3291034
cites work: Graph minors. III. Planar tree-width
cites work: A Menger-like property of tree-width: The finite case
cites work: Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
cites work: Q3491608
Recommended article: Menger's theorem for infinite graphs
Recommended article: A Menger-like property of tree-width: The finite case
Recommended article: On the girth of infinite graphs
Recommended article: Menger's theorem for infinite graphs with ends
Recommended article: On the metric dimension of infinite graphs
Recommended article: A Mengerian theorem for infinite graphs with ideal points
Recommended article: On the cycle space of an infinite 3-connected graph
Recommended article: Q3971998
Recommended article: On the Hadwiger number of infinite graphs
description: scientific article; zbMATH DE number 4105001