Akiyama–Exoo–Harary Linear Arboricity Conjecture

A linear forest is a graph whose connected components are paths, and the linear arboricity $la(G)$ of a graph $G$ is the minimum number of linear forests whose edge sets partition $E(G)$. Let $G$ be any graph with maximum degree $\Delta$.

Linear Arboricity Conjecture.

$$la(G)=\left\lceil\frac{\Delta+1}{2}\right\rceil.$$

The conjecture is known for several classes, including trees, complete graphs, and complete bipartite graphs, and it holds asymptotically for large maximum degree. The exact assertion remains open for general graphs.