(k,d)-choosability Of Planar Graphs

Let G =(V,E)be a graph.A proper k-coloring of G is an assignment of k different colors such that no adjacent vertices get the same color.If G has a proper k-coloring,then G is called be k-colorable.The chromatic number,denoted by ?(G),is defined to be the least positive integer k such that G is k-colorable.We say that L is an assignment for the graph G if it assigns a list L(v)of possible colors to each vertex v of G If G has a proper coloring ? such that ?(v)? L(v)for all vertices v,then we say that G is L-colorable or ? is an L-coloring of G.The graph G is k-choosable if it is L-colorable for every assignment L which satisfies |L(v)| ? k for all vertices v.The list chromatic number of G,?l(G)is defined to be the smallest positive integer k such that G is k-choosable.Motivated by forcing the list of the adjacent vertices to be somewhat separated,Kratochvil,Tuza,and Voigt firstly introduced the concept of choosability with separation in 1998.A(k,d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v)of at least k colors satisfying |L(x)? L(y)| ? d for each edge xy.A graph G is(k,d)-choosable if there is an L-coloring of G for every(k,d)-list assignment L.As we know,the celebrated Thomassen Theorem states that every planar graph is(5,5)-choosable.Voigt constructed non-(4,3)-choosable planar graphs.Kratochvil,Tuza and Voigt positively confirmed the(4,1)-choosability of planar graphs.The question of whether every planar graph is(4,2)-choosable seems to be a difficult and challenging open problem.Since the study of 3-choosability of planar graphs is the focus of graph coloring prob-lems.Recently,the research of(3,1)-choosability topic attracts much more attention.In this master thesis,we shall investigate(3,1)-choosability of planar graphs with restricted conditions.Our results will strengthen some known results.In Chapter 1,we first collect some basic notations which will be used frequently throughout the thesis.Then we present a chief survey in this direction and later state the main results that we obtain.In Chapter 2 and Chapter 3,we shall use classical Thomassen list coloring extension method to prove the following two results.(1)Every planar graph with neither 5-cycles nor normally adjacent 4-cycles is(3,1)-choosable.(2)Every planar graph with neither 6-cycles nor adjacent 4-and 5-cycles is(3,1)?choosable.