Linear Arboricity

The linear arboricity of a graph is the minimum number of linear forests whose union covers all edges of . Equivalently, it is the minimum number of edge-disjoint linear forests into which the edges of can be partitioned. For a finite graph, a linear forest is a forest each of whose connected components is a path graph. In an infinite graph, one-way and two-way infinite graph paths are also allowed. The notion was introduced by Harary (1970).

If denotes the maximum vertex degree of , then

(1)

where is the ceiling function. This lower bound is immediate since each linear forest has maximum vertex degree at most 2. Akiyama et al. (1981) conjectured that

(2)

a statement known as the linear arboricity conjecture, and proved every cubic graph has linear arboricity 2 and every 4-regular graph has linear arboricity 3. Alon (1988) proved an asymptotic form of the conjecture.

In general, linear arboricity is not determined solely by block values. It is true that

(3)

and conjectured that the inequality may be replaced with equality.

Aurichi et al. (2026) proved that the linear arboricity conjecture for finite graphs is equivalent to the same bound for all infinite graphs of finite maximum vertex degree. They also defined topological linear arboricity by requiring each linear forest, after adjoining the graph ends represented by its one-way infinite graph paths, to contain no subset homeomorphic to a circle in the space formed by adjoining all graph ends to . For finite maximum vertex degree, Aurichi et al. (2026) proved

(4)

Every -regular graph of girth at least also satisfies (Aurichi et al. 2026).