The List Linear Arboricity And Linear Choosability Of Cubic Graphs

The graph coloring problem is one of important branchs of graph theory. The thesis is divided into two parts, which consist of some results on list linear arboricity of cubic graphs and linear choosability of cubic graphs, respectively.The first part we study the notion of list linear arboricity lla(G) of a graph G and a conjecture proposed by An and Wu. A linear forest is a graph in which each component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G, introduced by Harary (1970).A list assignment L to the edges (or vertices) of G is the assignment of a set L(e) (?) N (or L(v) (?) N) of colors to every edge e (or v) of G, where N is the set of natural numbers. Furthermore, if for every edge (or vertex) e∈E(G) (or v∈V(G)), we have |L(e)| = k (or |L(v)| = k), then L is called a k-list assignment. Let C_φ= {φ(e)|e∈E(G)} (or C_φ= {φ(v)|v∈V(G)} ifφis a mapping from E(G) (or V(G)) to natural number N.If for any iφC_φ, there exists a coloringφsuch thatφ(e)∈L(e) for every edge e and G[φ^-1(i)] is a linear forest for, then ip is called a is linear L-coloring of G. If for every k-list assignment L, there exists a linear edge L-coloring, then G is called linear k-list colorable. The list linear arboricity lla(G) of a graph G is the minimum number k for which G is linear k-list colorable. It is obvious that la(G)≤lla(G). An and Wu posed the following conjecture.List Linear Arbricity Conjecture: For any graph G,In chapter 2, we confirm that this conjecture is ture for any cubic graph. The second part we investigate the notion of linear choosabihtyΛ^l(G) of a graph G, introduced by Esperet, Montassier, Raspaud. If ((?)i,j∈C_φ), G[φ^-1(i)]∪G[φ^-1(j)] is a linear forest, thenφis called a linear vertex L-coloring. If for every k-list assignment L, there exists a linear vertex L-coloring, then G is called linear vertex k-list colorable. The linear choosability numberΛ^l(G) of a graph G is the minimum number k for which G is hnear vertex k-list colorable.In chapter 3, we prove that if G is a cubic graph, thenΛ^l(G)≤5.