Covering and packing in graphs IV: Linear arboricity
Jin Akiyama, Geoffrey Exoo, Frank Harary · Networks · 1981
Abstract The linear arboricity of a graph is the minimum number of linear forests into which its lines can be decomposed. We find that the linear arboricity of every 4‐regular graph is 3. This result enables us to obtain bounds for the linear arboricity of any graph in terms of its maximum degree.