A linear forest is a forest in which every connected component is a line. The linear arboricity of an undirected graph is the minimum t such that the edge set can be partitioned into t subsets, each of which forms a linear forest.
Harari introduced this quantity as one of the covering invariants of graphs. Harari, Exoo and Akiyama (1981) made the following conjecture: the linear arboricity of any d regular graph is ceil(d+1)/2 (the lower bound is easy to prove; the non-trivial part is the upper bound).
Alon proved in 1988 that the linear arboricity of a d regular graph is at most d/2 + O(d^{3/4+\epsilon}) for any $\epsilon > 0$. The proof uses Lovasz Local Lemma and probabilistic method in very unexpected situations. We shall present this proof.
Link to paper: https://link.springer.com/article/10.1007/BF02783300
