Linear arboricity of robust expanders

Abstract

In 1980, Akiyama, Exoo, and Harary conjectured that any graph $G$ can be decomposed into at most $\lceil (\hat{I}”(G)+1)/2\rceil$ linear forests. We confirm the conjecture for robust expanders of linear minimum degree. As a consequence, the conjecture holds for dense quasirandom graphs of linear minimum degree as well as for large $n$-vertex graphs with minimum degree arbitrarily close to $n/2$ from above.

26pages