  The linear arboricity of a graph $G$, denoted by $\text{la}(G)$, is the
minimum number of edge-disjoint linear forests (i.e. forests in which every
connected component is a path) in $G$ whose union covers all the edges of $G$.
A famous conjecture due to Akiyama, Exoo, and Harary from 1980 asserts that
$\text{la}(G)\leq \lceil (\Delta(G)+1)/2 \rceil$, where $\Delta(G)$ denotes the
maximum degree of $G$. This conjectured upper bound would be best possible, as
is easily seen by taking $G$ to be a regular graph. In this paper, we show that
for every graph $G$, $\text{la}(G)\leq \frac{\Delta}{2}+O(\Delta^{2/3-\alpha})$
for some $\alpha > 0$, thereby improving the previously best known bound due to
Alon and Spencer from 1992. For graphs which are sufficiently good spectral
expanders, we give even better bounds. Our proofs of these results further give
probabilistic polynomial time algorithms for finding such decompositions into
linear forests.
