Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
Seog‐Jin Kim, Alexandr V. Kostochka, Douglas B. West, Hehui Wu, Xuding Zhu · Journal of Graph Theory · 2013
Abstract For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of over all subgraphs H with at least two vertices. Generalizing the Nash‐Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if , then G decomposes into forests with one having maximum degree at most d. The conjecture was previously proved for ; we prove it for and when and . For , we can further restrict one forest to have at most two edges in each component. For general , we prove weaker conclusions. If , then implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If , then implies that G decomposes into forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs.