Connected tree-width (Q722321)

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)\).