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; that is, it is a disjoint union of path graphs.

The linear arboricity of any graph of maximum degree

This conjecture would determine the linear arboricity exactly for graphs of odd degree, as in that case both expressions are equal.

For graphs of even degree it would imply that the linear arboricity must be one of only two possible values, but determining the exact value among these two choices is NP-complete.

, 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] However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger,

due to Ferber, Fox and Jain.

[2] In order for the linear arboricity of a graph to equal

must be even and each linear forest must have two edges incident to each vertex of degree

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

Thus, a graph whose linear arboricity equals

In a regular graph, there are no such vertices, and the linear arboricity cannot equal

Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly

Linear arboricity is a variation of arboricity, the minimum number of forests that the edges of a graph can be partitioned into.

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

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.