Proper List Coloring Of Planar Graphs

A list assignment of a graph G =(V,E)is a function L that assigns to each vertex v ? V a list L(v)of colors.An L-coloring of G is a function ?:V ? ?v?VL(v)such that ?(v)? L(v)for every v ? V and ?(u)??(v)whenever uv ? E.If G admits an L-coloring,then it is L-colorable.A graph G is k-choosable if it is L-colorable for every list assignment L with | L(v)|? k for every v?V.Graphs considered in this paper are finite,simple(i.e.,no loops and multi-edges)and undirected.Call a graph planar if the graph can be embedded into the plane so that its edges only meet at their ends.Any such a particular embedding of a planar graph is called a plane graph.Let G =(V,E)be a graph with the set of vertices V and the set of edges E,k be a positive integer.A mapping ?:V ?{1,2,...,k} is called a k-coloring of G if ?(x)? ?(y)whenever xy ? E.We call G is f-colorable if it admits a k-coloring.According to a k-coloring of G,we call that the fixed set {1,2,...,k} is the available color set for every vertex in G.Then we get the definition of list coloring based on the k-coloring of planar graph.A list assignment of a graph G =(V,E)is a function L that assigns to each vertex v ? V a list L(v)of colors.An L-coloring of G is a function A:V ??v?VL(v)such that ?(v)? L(v)for every v ? V and?(u)? ?(v)whenever uv ?E.If G admits an L-coloring,then it is L-colorable.A graph G is k-choosable if it is L-colorable for every list assignment L with | L(v)|? k for every v ? V.Since we may take L(v)= {1,2,...,k} for each v ?V,so if G is k-choosable,then G must be k-colorable.However,the opposite is generally not true.All 2-choosable graphs have been characterized by Erdos et al.[1].Thomassen[2]proved that every planar graph is 5-choosable.Voigt[3]showed that not all planar graphs are 4-choosable.Gutner[4]proved that the problems to determine whether a given planar graph is 3-or 4-choosable are NP-hard.So nice sufficient conditions for a planar graph to be 3-or 4-choosable are of certain interest.This master thesis consists of three chapters,focusing on the the study of proper list coloring,which has improved several previous results and laid the foundation for great guess.In the first chapter,we introduce some definitions and a brief survey of proper list coloring.In the second chapter,we introduce every planar graph without tri-angular 4-cycles is 4-choosable.In the third chapter,we introduce planar graphs with-out short cycles and having constraints on distance between triangles are 3-choosable.