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 G with maximum degree Δ is always at least ⌈ Δ / 2 ⌉ , 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 ⌊ ( Δ + 1 ) / 2 ⌋ . However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger, Δ / 2 + O ( Δ 2 / 3 ( log ⁡ Δ ) 1 / 3 ) .

In a regular graph, the linear arboricity cannot equal Δ / 2 because the endpoints of each path in one of the linear forests would not have two adjacent edges used by that forest. Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly ⌊ ( Δ + 1 ) / 2 ⌋ .

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. 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.