Linear arboricity

Relation to degree

The linear arboricity of a graph G with maximum degree \Delta is always at least \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 is that this lower bound is also tight: according to their conjecture, every graph has linear arboricity at most \lceil(\Delta+1)/2\rceil. However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger, \Delta/2 + O(\Delta^{2/3 - c}) for some constant c 0 due to Ferber, Fox and Jain.

In order for the linear arboricity of a graph to equal \Delta/2, \Delta must be even and each linear forest must have two edges incident to each vertex of degree \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 \Delta. Thus, a graph whose linear arboricity equals \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 \Delta/2. Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly \lceil(\Delta+1)/2\rceil.

Related problems

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.

Another related problem is Hamiltonian decomposition, the problem of decomposing a regular graph of even degree \Delta into exactly \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 \Delta/2.

Computational complexity

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. However, for cubic graphs and other graphs of maximum degree three, the linear arboricity is always two, and a decomposition into two linear forests can be found in linear time using an algorithm based on depth-first search.

References