Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

Abstract

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.