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 θ_T(G) or caterpillar thickness θ_C(G). If G has girth g with g5, then θ_T(G)n/g floor+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 θ_C, we prove that θ_C(G)(n-2)/4 ceil when G has girth at least 6 and is not a 6-cycle. For triangle-free graphs, we conjecture that θ_C(G)3n/8 ceil and prove it for outerplanar graphs. For 2-connected graphs with girth g, we conjecture that θ_C(G)n/g floor when n{6,g^2/2} and prove it for outerplanar graphs. All the bounds are sharp (sharpness in the 3n/8 ceil bound is shown only for n5 mod 8).