LINEAR 2-ARBORICITY OF THE COMPLETE GRAPH

Abstract

A linear k-forest is a graph whose components are paths with lengths at most k. The minimum number of linear k-forests needed to decompose a graph G is the linear k-arboricity of G and denoted by la(k) (G). In this paper, we settle the cases left in determining the linear 2-arboricity of the complete graph K(n). Mainly, we prove that la(2) (K(12t+10)) = la(2) (K(12t+11)) = 9t + 8 for any t >= 0.