Connected tree-width
type: Item
instance of: scholarly article
title: Connected tree-width
zbMATH Open document ID: 1399.05207
author: Reinhard Diestel
author: Malte Müller
published in: Combinatorica
publication date: 2018-07-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1211.7353
review text: The connected tree-width of a graph is the minimum width that a connected tree-decomposition of the graph can have. The authors prove that the connected tree-width of a graph is bounded above by a function of its tree-width and of the maximum length of its geodesic cycles. A bramble is a set of pairwise touching connected sets of vertices where two vertex sets touch if they share a vertex or the graph has an edge between them. A finite graph is shown to have small connected tree-width if and only if it has no bramble whose connected covers are large. Graphs of connected tree-width \(k\) are shown to be \(k\)-hyperbolic. If a graph has tree-width less than \(k\) and no geodesic cycle long than \(l\), and the graph is not a forest, then the tree-length of the graph is shown to be at most \(l(k-2)\).
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6909493
zbMATH Keywords: tree-decomposition
zbMATH Keywords: tree-width
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2964325321
arXiv ID: 1211.7353
cites work: Q4792909
cites work: Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
cites work: Tree-decompositions with bags of small diameter
cites work: Bounding Connected Tree-Width
cites work: Graph searching and a min-max theorem for tree-width
cites work: A Menger-like property of tree-width: The finite case
DOI: 10.1007/S00493-016-3516-5
description: scientific article