Decomposing a graph into forests

The fractional arboricity γf(G) of a graph G is the maximum of the ratio |E(G[X])|/(|X|−1) over all the induced subgraphs G[X] of G. In this paper, we propose a conjecture which says that every graph G with decomposes into k+1 forests, and one of the forests has maximum degree at most d. We prove two special cases of this conjecture: if G is a graph with fractional arboricity at most , then G decomposes into a forest and a matching. If G is a graph with fractional arboricity at most , then G decomposes into a forest and a linear forest. In particular, every planar graph of girth at least 8 decomposes into a forest and a matching, and every planar graph of girth at least 6 decomposes into a forest and a linear forest. This improves earlier results concerning decomposition of planar graphs, and the girth condition is sharp, as there are planar graphs of girth 7 which do not decompose into a forest and a matching, and there are planar graphs of girth 5 which do not decompose into a forest and a linear forest. The bound in the conjecture above is sharp: We shall show that for any ϵ>0, there is a graph G with , and yet G cannot be decomposed into k forests plus a graph of maximum degree at most d. On the other hand, we show that for any positive integer k and real number 0⩽ϵ<1, every graph G with γf(G)⩽k+ϵ decomposes into k forests plus a graph of maximum degree at most .