On linear k-arboricity (Q761470)

The authors study the parameter \(la_ k(G)\), defined as the minimum integer c such that E(G) can be partitioned into c classes, each being a union of paths of length at most k. Thus \(la_ 1(G)\) is the chromatic index of G (and hence \(la_ 1(G)\leq \Delta (G)+1\)); the parameter \(la_{n-1}(G)\) (where n is the number of vertices of G) has been called linear arboricity [cf. \textit{F. Harary}, Ann. New York Acad. Sci. 175, 198-205 (1970; Zbl 0226.05119)]. For \(k\geq 2\), the authors prove that \(la_ k(G)\leq \Delta (G)\); they also give a lower bound on \(la_ k(G).\) The main results of the paper deal with the special cases of cubic graphs and complete graphs. For cubic graphs, the general bounds imply that \(la_ 2(G)=3\geq la_ 3(G)\geq...\geq la_{n-1}(G)=2\); the authors then study those cubic graphs with \(la_ 3(G)=2.\) Their recognition is an NP- complete problem, but they include cubic graphs whose square is 4- chromatic and those cubic planar graphs in which all face boundaries have length divisible by k, \(k=3\) or 4 (those with \(k=5\) having \(la_ 4(G)=2\)). They conjecture that all cubic graphs have \(la_ 5(G)=2.\) For complete graphs, the general lower bound is shown (using resolvable graph designs) to be the exact value of \(la_ 2(K_ n)\), with the possible exception of \(n\equiv 10\) and 11(mod 12).