The linear arboricity of graphs

Alinear forest is a forest in which each connected component is a path. Thelinear arboricity la(G) of a graphG is the minimum number of linear forests whose union is the set of all edges ofG. Thelinear arboricity conjecture asserts that for every simple graphG with maximum degree Δ=Δ(G), $$la(G) \leqq [\frac{{\Delta + 1}}{2}].$$ . Although this conjecture received a considerable amount of attention, it has been proved only for Δ≦6, Δ=8 and Δ=10, and the best known general upper bound for la(G) is la(G)≦⌈3Δ/5⌉ for even Δ and la(G)≦⌈(3Δ+2)/5⌉ for odd Δ. Here we prove that for everyɛ>0 there is a Δ0=Δ0(ɛ) so that la(G)≦(1/2+ɛ)Δ for everyG with maximum degree Δ≧Δ0. To do this, we first prove the conjecture for everyG with an even maximum degree Δ and withgirth g≧50Δ.