The linear arboricity conjecture for graphs of low degeneracy.

A $k$-linear coloring of a graph $G$ is an edge coloring of $G$ with $k$ colors so that each color class forms a linear forest -- a forest whose each connected component is a path. The linear arboricity $\chi_l'(G)$ of $G$ is the minimum integer $k$ such that there exists a $k$-linear coloring of $G$. Akiyama, Exoo and Harary conjectured in 1980 that for every graph $G$, $\chi_l'(G)\leq \left \lceil \frac{\Delta(G)+1}{2}\right\rceil$ where $\Delta(G)$ is the maximum degree of $G$. First, we prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture in some classes of graphs like cubic graphs and triangle-free planar graphs for which the conjecture was already known to be true. Next, for every 2-degenerate graph $G$, we show that $\chi'_l(G)=\left\lceil\frac{\Delta(G)}{2}\right\rceil$ if $\Delta(G)\geq 5$. We conjecture that this equality holds also when $\Delta(G)\in\{3,4\}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs. All our proofs can be converted into linear time algorithms.