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

where is the ceiling function. This lower bound is immediate since each linear forest has maximum vertex degree at most 2. The linear arboricity conjecture proposes the upper bound . Akiyama et al. (1981) proved that every cubic graph has linear arboricity 2 and every 4-regular graph has linear arboricity 3.

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

and conjectured that the inequality may be replaced with equality.