On The Linear Arboricity Conjecture

Sreejata Kishor Bhattacharya
Friday, 11 Nov 2022, 16:00 to 17:00
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