\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Qi Liu and Douglas B. West}
%
%
\medskip
\noindent
%
%
{\bf Tree-Thickness and Caterpillar-Thickness under Girth Constraints}
%
%
\vskip 5mm
\noindent
%
%
%
%
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 {\it tree thickness} $\theta_{\bf T}(G)$ or {\it
caterpillar thickness} $\theta_{\bf C}(G)$.  If $G$ has girth $g$ with
$g\ge 5$, then $\theta_{\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 $\theta_{\bf
C}$, we prove that $\theta_{\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 $\theta_{\bf C}(G)\le\lceil{3n/8}\rceil$
and prove it for outerplanar graphs.  For $2$-connected graphs with
girth $g$, we conjecture that $\theta_{\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$).

\bye

.