Linear arboricity

In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned into. Here, a linear forest is an acyclic graph with maximum degree two, i.e., a disjoint union of path graphs.

The linear arboricity of a graph ${\displaystyle G}$ with maximum degree ${\displaystyle \Delta }$ is always at least ${\displaystyle \lceil \Delta /2\rceil }$, because each linear forest can use only two of the edges at a maximum-degree vertex. The linear arboricity conjecture of Akiyama, Exoo & Harary (1981) is that this lower bound is also tight: according to their conjecture, every graph has linear arboricity at most ${\displaystyle \lfloor (\Delta +1)/2\rfloor }$. However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger, ${\displaystyle \Delta /2+O(\Delta ^{2/3}(\log \Delta )^{1/3})}$.

...
Wikipedia