Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k≤ 2
For a loopless multigraph G , the fractional arboricity Arb ( G ) is the maximum of | E ( H ) | | V ( H ) | − 1 over all subgraphs H with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if Arb ( G ) ≤ k + d k + d + 1 , then G decomposes into k + 1 forests with one having maximum degree at most d . The conjecture was previously proved for d = k + 1 and for k = 1 when d ≤ 6 . We prove it for all d when k ≤ 2 , except for ( k , d ) = ( 2 , 1 ) .