The k-linear arboricity of a graph G is the minimum number of forests whose connected components are paths of length at most k which partition E(G). Motivated by this index, we investigate a variation of this idea for d-regular graphs. Namely, we define a d-regular graph G to be (l, k)-linear arborific if E(G) can be partitioned into edge sets of l linear forests consisting of paths of length at most k. By extending an inductive tool developed by Jackson and Wormald, we determine, for d ≥ 4, values of k such that every d-regular graph is (d - l, k)-linear arborific.
|Number of pages||10|
|Publication status||Published - 15 May 1998|