More on the linear k-arboricity of regular graphs
Robert E. L. Aldred, Nicholas Wormald · 1998
Bermond et al. [5] conjectured that the edge set of a cubic graph G can be partitioned into two linear k-forests, that is to say two forests whose connected components are paths of length at most k, for all k;::: 5. That the statement is valid for all k;::: 18 was shown in [8] by Jackson and Wormald. Here we improve this bound to k> {7 if X' ( G) = 3;- 9 otherwise. The result is also extended to d-regular graphs for d> 3, at the expense of increasing the number of forests to d- 1. All graphs considered will be finite. We shall refer to graphs which may contain loops or multiple edges as multigraphs and reserve the term graph for those which do not. A linear forest is a forest each of whose components is a path. The linear arboricity of a graph G, defined by Harary [7], is the minimum number of linear forests required to partition E(G) and is denoted by la(G). It was shown by Akiyama, Exoo and Harary [1] that la ( G) = 2 when G is cubic. A linear k-forest is a forest consisting