pith. sign in

arxiv: 1503.01592 · v2 · pith:4GRZ3OXSnew · submitted 2015-03-05 · 🧮 math.CO · cs.DM

Bounding connected tree-width

classification 🧮 math.CO cs.DM
keywords connectedtree-widthdiestelgraphorderulleranalogueasserting
0
0 comments X
read the original abstract

Diestel and M\"uller showed that the connected tree-width of a graph $G$, i.e., the minimum width of any tree-decomposition with connected parts, can be bounded in terms of the tree-width of $G$ and the largest length of a geodesic cycle in $G$. We improve their bound to one that is of correct order of magnitude. Finally, we construct a graph whose connected tree-width exceeds the connected order of any of its brambles. This disproves a conjecture by Diestel and M\"uller asserting an analogue of tree-width duality.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.