Tree-thickness and caterpillar-thickness under girth constraints
type: Item
instance of: scholarly article
title: Tree-thickness and caterpillar-thickness under girth constraints
zbMATH Open document ID: 1163.05321
author: Qi Liu
author: Douglas B. West
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129981
full work available at URL: v15i1r93.html
review text: 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\)).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 5540998
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540998