Originators: Q. Liu and D.B. West (presented by D. West - REGS 2009)
Definitions: A decomposition of a graph G is a family of edge-disjoint subgraphs of G whose union is G. For a hereditary family F, the F-thickness of a graph G, written θF(G), is the minimum number of subgraphs in a decomposition of G using only subgraphs in F. The girth of a graph, is the minimum length of a cycle in the graph; the girth of a forest is infinite. A caterpillar is a tree such that the result of deleting all leaves is a path.
Background: The original use of "thickness" was for F being the family of planar graphs, where the subgraphs in the decomposition can be viewed as planar "layers". When F is the family of all forests, the parameter is called "arboricity"; Nash-Williams [N] and Edmonds [E] proved that always the arboricity of a graph G equals maxH⊆G⌈|E(H)| / (|V(H)-1)⌉.
Here we consider tree thickness, caterpillar thickness, and path thickness, which result when F is the set T of all trees, the set C of all caterpillars, or the set P of all paths, respectively. Extremal problems for decomposition seek the maximum of θF(G) when G lies in a particular family G of graphs. The natural initial family to consider is the family of all n-vertex graphs. Restricting the family F of allowable subgraphs potential increases the extremal value. Restricting the family G potentially decreases it. Here our subgraphs are connected, and it is natural to restrict G to connected graphs.
When G is a connected n-vertex graph, Chung [C] proved that θT(G)≤⌈n/2⌉, which holds with equality for the complete graph Kn. In fact, her proof uses only caterpillars with diameter at most 4 to decompose each such graph, so this bound holds also for θC(G). The statement that the bound also holds for path-thickness is Gallai's Conjecture, which remains open. Here we seek improvements in the bounds when a girth threshold is imposed on the input. These problems are stated in Liu-West [LW].
Conjecture 1: If G is a connected triangle-free graph with n vertices, then θT(G)≤⌊n/4⌋+1.
Problem 2: What are the maximum values of the caterpillar-thickness and the path-thickness for connected triangle-free graphs with n vertices?
Comments: Liu and West [LW] proved that θT(G)≤⌊n/g⌋+1 when G is a connected n-vertex graph with girth g when g≥5; the proof is not valid for g=4. The bound is best possible due to the n-vertex graph consisting of (n-1)/g disjoint g-cycles plus one vertex having one neighbor in each g-cycle. (Minor modifications of this are used for other congruence classes of n modulo g.)
The same paper proved that θC(G)≤⌈(n-2)/4⌉+1 when G is a connected n-vertex graph with girth at least 6 and n>6. Equality holds when G is the tree obtained from the star K1,m by subdividing each edge once (when m is odd).
Lovász [L] proved that every n-vertex graph decomposes into at most ⌊n/2⌋ subgraphs that are paths or cycles; this proves that the bound in Gallai's Conjecture is true when at most one vertex in G has even degree. Let H be the subgraph of G induced by the vertices having even degree in G. Pyber [P] proved that θP(G)≤⌈n/2⌉ when H is a forest. Fan [F] proved that the bound still holds under other conditions; as a corollary, θP(G)≤⌈n/2⌉ whenever each block of H is a triangle-free graph with maximum degree at most 3.
References:
[C] Chung, F. R. K. On partitions of graphs into trees. Discrete Math. 23
(1978), no. 1, 23--30.
[F] Fan, Genghua Path decompositions and Gallai's conjecture. J. Combin. Theory
Ser. B 93 (2005), no. 2, 117--125.
[LW] Liu, Qi; West, Douglas B. Tree-thickness and caterpillar-thickness under
girth constraints. Electron. J. Combin. 15 (2008), no. 1, Research Paper 93,
11 pp.
[L] L. Lovász, On covering of graphs, in: P. Erdős, G. Katona
(Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231--236.
[P] Pyber, L. Covering the edges of a connected graph by paths. J. Combin.
Theory Ser. B 66 (1996), no. 1, 152--159.