Linear K-arboricity Of Some Graphs

A linear k-forest is a graph whose components are paths of length at most k. The linear k-arboricity of a graph G, denoted by la,k(G), is the least number of linear k-forests needed to decompose G. The linear k-rboricity is a natural generalization of edge coloring. Clearly, a linear1-forest is induced by a matching, and lα1(G) is the edge chromatic number, or chromatic index, χ’(G) of a graph G. Moreover, the linear k-rboricity lαk(G) is also a refinement of the ordinary linear arboricity la(G)(or lα∞G)) of a graph G. The ordinary linear arboricity of a graph G is the least number of linear forests (a graph whose components are paths) needed to decompose G, which is the case when every component of each forest is a path with no length constraint.A graph G is m-partite if its vertex set V(G) can be partitioned into m (possibly empty) independent sets called partite sets of G. A complete m-partite graph G is a m-partite graph having the additional property that the edge uv E∈(G) if and only if u and v belong to different partite sets. When m>2, we write Kn1,n2,…,nm for the complete m-partite graph with partite sets of sizes n1,n2,…,nm. Moreover, if n1=n2=…=nm=n, then it is called a balanced complete m-partite graph and denoted by Km(n) A complete graph is a simple graph in which any two vertices are adjacent. Let k be a positive integer number, if one of the following conditions is true, then G has property Pk:(1)δ(G)≤1:(2)M*(G)≤κ;(3)G has a (2, k+1)-alternating cycle. If each subgraph of G has property Pk, then G is called a Pk--genetic graph.According to the contents, this paper is divided into four chapters:In the first chapter, it introduces the background, significance of paper and the present studying of linear k-arboricity of graphs and some preparative theories.In the second chapter, it is studied the linear4-arboricity of balanced complete bipartite graph, it is determined that the exact value of the linear4-arboricity of balanced complete bipartite graph when n≡0(mod5).In the third chapter, it is studied a special plane graph, it is determined that a upper bound of linear2-arboricity of a plane graph without4-cycles and5-cycles.In the fourth chapter, it is studied the Mycielski graph of complete graph Kn, it is deter-mined that the exact value of the linear3-arboricity and linear arboricity of the Mycielski graph of complete graph Kn with even order.