The Linear 2- and 4-Arboricity of Complete Bipartite Graph

A linear -forest of an undirected graph is a subgraph of whose components are paths with lengths at most . The linear -arboricity of , denoted by ( ), is the minimum number of linear -forests needed to decompose . In case the lengths of paths are not restricted, we then have the linear arboricity of , denoted by ( ). In this paper, the exact value of the linear 2- and 4-arboricity of complete bipartite graph for some and is obtained. 1. Introduction Throughout this paper, all graphs considered are finite, undirected, and simple. Let represent the set of natural numbers and let denote the set . A graph is -partite ( ), if it is possible to partition the vertex set into independent sets (called partite sets) such that every edge of joins the vertices in different partite sets. A complete -partite graph is one that is simple and in which each vertex is joined to every vertex that is not in the same subset, which is denoted by if for . For , such graphs are called complete bipartite graphs and denoted by . When , we denote by , which is called balanced complete -partite graph. For , such graphs are called balanced complete bipartite graphs and are denoted by . On the other hand, a graph with order , in which any pair of different vertices are adjacent, is a complete graph, denoted by . Other notations and terminology in the paper are the same as in [1]. A？？decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list. If a graph has a decomposition , then we say that decompose or can be decomposed into . Furthermore, a linear -forest is a forest whose components are paths of length at most . The linear -arboricity of a graph , denoted by , is the least number of linear -forests needed to decompose . The notion of linear -arboricity of a graph was first introduced by Habib and Peroche [2]. It is a natural generalization of edge coloring. Clearly, a linear -forest is induced by a matching, and is the chromatic index of a graph . Moreover, the linear -arboricity is also a refinement of the ordinary linear arboricity (or ) which is the case when every component of each forest is a path with no length constraint. By the way, the notion of linear arboricity was introduced earlier by Harary in [3]. In 1982, Habib and Péroche [4] proposed the following conjecture for an upper bound on . Conjecture 1 (see [4]). If is a graph with maximum degree and , then For , this is Akiyama’s conjecture [5]. Conjecture 2 (see [5]). Consider？？ . So far, there have been a lot of results on the verification of Conjecture 1 in the