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. Here, a linear forest is a forest
each of whose connected components is a path graph.
The notion was introduced by Harary (1970).
If 
denotes the maximum degree of 
, then
![[(Delta(G))/2]<=la(G).](/images/equations/LinearArboricity/NumberedEquation1.svg) |
(1)
|
This lower bound is immediate since each linear forest has maximum degree at most 2. Akiyama, Exoo, and Harary (1981) conjectured that
![la(G)<=[(Delta(G)+1)/2],](/images/equations/LinearArboricity/NumberedEquation2.svg) |
(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
![la(G)>=max(max_(1<=i<=k)la(B_i),[(Delta(G))/2]),](/images/equations/LinearArboricity/NumberedEquation3.svg) |
(3)
|
and conjectured that the inequality may be replaced with equality.
