The Linear Arboricity And Linear K-arboricity Of Graphs

The coloring is the focus of research in the graph theory. Aκ-edge coloring of a graph G is a mapping f from E(G) to{1,2,…,κ}. With respect to a givenκ-edge coloring, Ei is denoted by the set of all edges of G colored with i, and G[Ei] is denoted by the subgraph induced by Ei in G. If Ei is a matching for every 1≤i≤κ, then f is called a properκ-edge coloring. The edge chromatic numberχ'(G) of a graph G is the minimum number k for which G has a properκ-edge coloring. If all components of G[Ei] are paths, then f is called aκ-linear coloring. The linear arboricity of a graph G, denoted by la(G), is the minimum number k for which G has aκ-linear coloring.Aκ-coloring of a graph G is a mapping f from V(G) to{1,2,…, k}. With respect to a givenκ-coloring, Vi is denoted by the set of all vertices of G colored with i, and G[Vi] is denoted by the subgraph induced by Vi in G. If Vi is an independent set for every 1≤i≤κ, then f is called a properκ-coloring. The chromatic numberχ'(G) of a graph G is the minimum number k for which G has a properκ-coloring. If all components of G[Vi] are paths, then f is called a pathκ-coloring. The vertex linear arboricity of a graph G, denoted by vla(G), is the minimum number k for which G has a pathκ-coloring.A linearκ-forest of a graph G is a subgraph of G whose components are paths with lengths at most k. The linearκ-arboricity of G, denoted by laκ(G), is the minimum number of linearκ-forests needed to partition the edge set E(G) of G. In fact, It is a natural generalization of edge coloring. Clearly, a linear 1-forest is induced by a matching, and la1(G) is the edge chromatic number, or chromatic index,χ'(G) of a graph. In case that the lengths of paths in linearκ-arboricity are not restricted, we then have the linear arboricity of G, denoted la∞(G) by la(G).A complete m-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Κn1,n2,…nm if| Vi|= ni(i= 1,2,…, m). When n1=n2=…=nm=n, we denoteΚn1,n2,…,nm by Km(n), which is called balanced complete m-partite graph. A subset S of [n]={0,1,…, n-1} is said to be 2-stable if 2≤| x - y|≤n - 2 for any two distinct elements x and y, i.e., S does not contain two consecutive numbers in the cyclic ordering of [n]. The Schrijver graph SG(n, k) is defined as follows. Its vertices are thoseκ-element subsets of the set[n]={0,1,…,n - 1} that do not contain cyclically consecutive elements i,i+1 or n - 1,0. Two such vertices are adjacent if they represent disjointκ-subsets.The Cartesian product of m graphs G1, G2,…, Gm is the graph G= G1□G2□…□Gm whose vertex set is (?) two vertices (u1,u2,…,um) and (v1,v2,…,vm) are ad-jacent if and only if ujvj∈E(Gj) for some j and ui= vi for all other i≠j. When Gi=G for all i, we use Gm to denote G1□G2□…□Gm. A Hamming graph is the Cartesian productΚn1□Κn2□…□Κnm of complete graphsΚn1,Κn2,…,ΚnmLetΚn(m),Κnm, SG(n,k) be the balanced complete n-partite graph, Hamming graphΚn□Κn□…□Κn and Schrijver graph. Denote the maximum degree of graph G by△(G).This paper is divided into four chapters:In chapter 1, some definitions, notations and the development of linear arboricity and linearκ-arboricity are introduced.In chapter 2, the linear arboricity of Schrijver graph SG(2k+2,κ) is studied. The config-uration of SG(2k+2, k) is obtained. Furthermore, two results are obtained.Conclusion 2. vla(SG(2k+2,κ))= 2.In chapter 3, the linearκ-arboricity ofΚn(m) andΚnm is studied. We take k= n-1, the following two nice results are establishedConclusion 3. For balanced complete n-partite graphΚn(m),Conclusion 4. For Hamming graphΚnm,In chapter 4, we study the linear 2-arboricity of Cnm, and the linear 4-arboricity ofΚ6n,4n,Κ6n+1,4n,Κ6n,4n+1.The following results are obtained.Conclusion 5. For complete bipartite graph and Cartesian product Cnm, it is obtained that(a) (?) ,where n≡0(mod 3).(b) la4(Κ6n,4n)= 3n.(c) la4(Κ6n+1,4n)= la4(Κ6n,4n+1)= 3n+1, where n is odd.