Linear arboricity of degenerate graphs

Abstract

A linear forest is a union of vertex-disjoint paths, and the linear arboricity of a graph $G$, denoted by $\mathrm{la}(G)$, is the minimum number of linear forests needed to partition the edge set of $G$. Clearly, $\mathrm{la}(G)\ge \lceil \Delta (G)/2\rceil$ for a graph $G$ with maximum degree $\Delta (G)$. On the other hand, the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that $\mathrm{la}(G)\le \lceil (\Delta (G)+1)/2\rceil$ for every graph $G$. This conjecture has been verified for planar graphs and graphs whose maximum degree is at most $6$, or is equal to $8$ or $10$. Given a positive integer $k$, a graph $G$ is $k$-degenerate if it can be reduced to a trivial graph by successive removal of vertices with degree at most $k$. We prove that for any $k$-degenerate graph $G$, $\mathrm{la}(G)=\lceil \Delta (G)/2\rceil$ provided $\Delta (G)\ge 2k^2-k$.

15 pages, 1 figure