THE LINEAR 2-ARBORICITY OF COMPLETE BIPARTITE GRAPHS

Abstract

A forest in which every component is path is called a path forest. A family of path forests whose edge sets form a partition of the edge set of a graph G is called a path decomposition of a graph G. The minimum number of path forests in a path decomposition of a graph G is the linear arboricity of G and denoted by l(G). If we restrict the number of edges in each path to be at most k then we obtain a special decomposition. The minimum number of path forests in this type of decomposition is called the linear k-arboricity and denoted by la(k)(G). In this paper we concentrate on the special type of path decomposition and we obtain the answers for la2(G) when G is K(n,n). We note here that if we restrict the size to be one, the number la1(G) is just the chromatic index of G.