Tree-thickness and caterpillar-thickness under girth constraints (Q1010820): Difference between revisions

Summary: 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 \(\theta_{\mathbf T}(G)\) or caterpillar thickness \(\theta_{\mathbf C}(G)\). If \(G\) has girth \(g\) with \(g\geq 5\), then \(\theta_{\mathbf T}(G)\leq \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 \(\theta_{\mathbf C}\), we prove that \(\theta_{\mathbf C}(G)\leq\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 \(\theta_{\mathbf C}(G)\leq\lceil{3n/8}\rceil\) and prove it for outerplanar graphs. For 2-connected graphs with girth \(g\), we conjecture that \(\theta_{\mathbf C}(G)\leq \lfloor{n/g}\rfloor\) when \(n\geq\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\)).