Tree-thickness and caterpillar-thickness under girthconstraintsQi Liu∗Douglas B. West†AbstractWe study extremal problems for decomposing a connected n-vertex graph G intotrees 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 g ≥ 5, then θT(G) ≤⌊n/g⌋ + 1. This also holds for girth 4 when additional subgraphs are forbidden.We study θC(G) when G is outerplanar. If g ≥ 4, then θC(G) ≤ ⌈3n/8⌉; sharp forn ≡ 5 mod 8. If g ≥ 5, then θC(G) ≤ ⌈3n/10⌉; sharp for n ≡ 6 mod 10. If G is 2-connected, then the bounds are ⌊n/g⌋ when n ≥ g2/2,jn−gg−2kwhen 3g − 4 ≤ n ≤ g2/2,and 2 when g ≤ n ≤ 3g − 4.If g ≥ 6 and n > 6, outerplanar or not, then θC(G) ≤ ⌈(n − 2)/4⌉. All these boundsfor θT(G) and θC(G) are sharp for n as specified.1 IntroductionA decomposition of a graph G is a set of pairwise edge-disjoint subgraphs with union G. Westudy decompositions of connected n-vertex graphs (general, planar, or outerplanar) into thefewest trees or the fewest caterpillars.The complete graph Kndecomposes into ⌈n/2⌉ paths and no fewer. Gallai famouslyconjectured that every connected n-vertex graph decomposes into ⌈n/2⌉ paths. Chu ng [1]∗Mathematics Department, University of Illinois, Urbana, IL 61801, [email protected]. Work sup-ported in the 2004 REGS Program of the University of Illinois.†Mathematics Department, University of Illinois, Urbana, IL 61801, [email protected]. Work sup-ported in part by the NSA under Award No. MDA904-03-1-0037.1proved that ⌈n/2⌉ trees suffice. In fact, her proof decomposes every connected n-vertexgraph into ⌈n/2⌉ caterpillars of diameter at most 4. A caterpillar is a tree having a singlepath (the spine) that contains at least one endpoint of every edge; equivalently, deleting theleaves yields a path. This class is intermediate between paths and trees. The connectednesscondition is needed because n/3 disjoint triangles do not decompose into fewer than 2n/3trees. We study always connected graphs, and we use n for the number of vertices.Given a class F of graphs, the F-decomposition number or F-thickness of a graph G,written θF(G), is the minimum size of a decomposition of G into subgraphs that lie in F.We seek the maximum of θFover graphs in some class G. We can refine such problems byseeking tighter bounds over classes smaller than G or by restricting the family F. Let θTand θCdenote the tree-thickness and caterpillar-thickness, resp ectively.For connected graphs, the maximum tree-thickness ⌈n/2⌉ is attained by Kn. Forbiddingtriangles excludes this extremal graph. The girth of a graph is the length of a shortest cycle.For g ≥ 5, we prove in Theorem 4 that θT(G) ≤ ⌊n/g⌋ + 1 when G is connected and hasgirth g, and equality is achievable. The conclusion also holds when g = 4 among graphscontaining no subdivision of K2,3with girth 4.In a larger class of graphs with girth 4, we obtain a weaker upper bound that neverthelessis tighter than the bound for general graphs. We prove in Theorem 5 that θT(G) ≤ ⌈n/3⌉when G is a connected graph with girth 4 not containing the graph obtained from K4,3bydeleting one ed ge. We know of no connected graph with girth 4 having tree-thickness morethan ⌊n/4⌋ + 1 and conjecture that ⌊n/4⌋ + 1 is the maximum.We next turn to caterpillar-thickness. Even on special families of planar graphs, θCmaybe larger than the maximum of θTon more general families. A graph is outerplanar if ithas an embedding in the plane with all vertices lying on the unbounded face. A cactus is aconnected graph in which every edge appears in at most one cycle; equivalently, every blockis an edge or a cycle. Every cactus is outerplanar.Always θT(G) ≤ θC(G) ≤ ⌈n/2⌉ (by Chung’s proof), with equality throughout whenn ≡ 4 mod 6 for special cacti with triangles (Example 1). Forbidd ing triangles tightens thebound. We p rove in Theorem 7 that θC(G) ≤ ⌈3n/8⌉ when G is outerplanar and triangle-free, sharp when n ≡ 5 mod 8. With girth at least 5, a similar proof yields θC(G) ≤⌈3n/10⌉, sharp when n ≡ 6 mod 10. Regardless of outerplanarity, girth at least 6 forcesthc(G) ≤ ⌈(n − 2)/4⌉ when n > 6 (Theorem 9), achieved using trees (Example 2).2The extremal graphs presented in Example 1 are cacti. When we exclude cacti by consid-ering only 2-connected outerplanar graphs, the bound on caterpillar-thickness tightens. Weprove in Theorem 6 that if G is a 2-connected n-vertex outerplanar graph with girth g, thenthe maximum possible value of θC(G) is ⌊n/g⌋ if n ≥ g2/2, isjn−gg−2kif 3g − 4 ≤ n ≤ g2/2,and is 2 if g ≤ n ≤ 3g − 4.It is natural to ask whether the bounds on caterpillar thickness of outerplanar graphswith fixed girth continue to hold when all planar graphs with that girth are allowed. Thesequestions remain open. That is, is it true that θC(G) ≤ ⌊n/g⌋ whenever G is a 2-connectedplanar graph with girth at least g and that θC(G) ≤ ⌈3n/8⌉ whenever G is a connectedplanar graph with girth at least 4?2 Lower Bound ConstructionsIn this section we present examples showing that the bounds in our later theorems are sharp.Example 1 Let Hk,gdenote the cactus with kg + 1 vertices formed from k disjoint g-cycles by adding one vertex having one neighbor in each cycle (see Figure 1). The cut-edges in Hk,gimply that only one tree in a decomposition can extend out from each cycle.However, two trees must be used within each cycle. Hence at least k trees are confined tothe cycles, and at least one more tree must be used. There is such a decomposition, soθT(Hk,g) = k + 1 = ⌊n/g⌋ + 1.• • ••CgCgCgx· · ·kFigure 1: The graph Hk,gThis decomposition of Hk,gis unavailable for caterpillar thickness, since the one largetree has an edge on each cycle and hence is not a caterpillar (when k ≥ 3). A caterpillar in3Hk,ghas edges in at most two of the cycles, because a caterpillar cannot have three paths oflength 2 with a common endpoint. Therefore, since only k paths can start along and departfrom a cycle, the best we can do is save ⌊k/2⌋ by combining into pairs the paths that leavethe cycles. Thus θC(Hk,g) = 2k − ⌊k/2⌋ = ⌈3k/2⌉.More generally, let n = kg + r, where 1 ≤ r ≤ g. Note that k = ⌊(n − 1)/g⌋. Let x bethe central vertex of Hk,g. When k is even and r = 3, form H′k,gby appending a path of