Tree-Thickness and Caterpillar-Thickness under Girth Constraints - Liu, Qi; West, Douglas B. (The Electronic Journal of Combinatorics, 2008)
We study extremal problems for decomposing a connected $n$-vertex graph $G$ into trees or into caterpillars. The least size of such a decomposition is the tree thickness $θ_{\bf T}(G)$ or caterpillar thickness $θ_{\bf C}(G)$. If $G$ has girth $g$ with $g\ge 5$, then $θ_{\bf T}(G)\le \lfloor{n/g}\rfloor+1$. We conjecture that the bound holds also for $g=4$ and prove it when $G$ contains no subdivision of $K_{2,3}$ with girth 4. For $θ_{\bf C}$, we prove that $θ_{\bf C}(G)\le\lceil{(n-2)/4}\rceil$ when $G$ has girth at least $6$ and is not a $6$-cycle. For triangle-free graphs, we conjecture that $θ_{\bf C}(G)\le\lceil{3n/8}\rceil$ and prove it for outerplanar graphs. For $2$-connected graphs with girth $g$, we conjecture that $θ_{\bf C}(G)\le \lfloor{n/g}\rfloor$ when $n\ge\max\{6,g^2/2\}$ and prove it for outerplanar graphs. All the bounds are sharp (sharpness in the $\lceil{3n/8}\rceil$ bound is shown only for $n\equiv 5$ mod $8$).