Linear Arboricity Conjecture

The linear arboricity conjecture states that every finite graph has

(1)

where is its linear arboricity, is its maximum vertex degree, and is the ceiling function (Akiyama et al. 1981). Equivalently, its edges can be partitioned into at most this many linear forests, each a forest whose connected components are path graphs.

The elementary lower bound is

(2)

since each linear forest has maximum vertex degree at most 2. Thus the conjectured upper bound is either this lower bound or one more. Akiyama et al. (1981) established the conjecture for cubic graphs and 4-regular graphs, and Alon (1988) proved an asymptotic form.

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

(3)

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