Linear arboricity

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 \lceil (\Delta +1)/2\rceil }$.[1] However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger, ${\displaystyle \Delta /2+O(\Delta ^{2/3-c})}$ for some constant ${\displaystyle c>0}$ due to Ferber, Fox and Jain.[2]

In order for the linear arboricity of a graph to equal ${\displaystyle \Delta /2}$, ${\displaystyle \Delta }$ must be even and each linear forest must have two edges incident to each vertex of degree ${\displaystyle \Delta }$. But at a vertex that is at the end of a path, the forest containing that path has only one incident edge, so the degree at that vertex cannot equal ${\displaystyle \Delta }$. Thus, a graph whose linear arboricity equals ${\displaystyle \Delta /2}$ must have some vertices whose degree is less than maximum. In a regular graph, there are no such vertices, and the linear arboricity cannot equal ${\displaystyle \Delta /2}$. Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly ${\displaystyle \lceil (\Delta +1)/2\rceil }$.

Linear arboricity is a variation of arboricity, the minimum number of forests that the edges of a graph can be partitioned into. Researchers have also studied linear k-arboricity, a variant of linear arboricity in which each path in the linear forest can have at most k edges.[3]

Another related problem is Hamiltonian decomposition, the problem of decomposing a regular graph of even degree ${\displaystyle \Delta }$ into exactly ${\displaystyle \Delta /2}$ Hamiltonian cycles. A given graph has a Hamiltonian decomposition if and only if the subgraph formed by removing an arbitrary vertex from the graph has linear arboricity ${\displaystyle \Delta /2}$.

Unlike arboricity, which can be determined in polynomial time, linear arboricity is NP-hard. Even recognizing the graphs of linear arboricity two is NP-complete.[4] However, for cubic graphs and other graphs of maximum degree three, the linear arboricity is always two,[1] and a decomposition into two linear forests can be found in linear time using an algorithm based on depth-first search.[5]