The Choosability Of Graphs

Let G be a finite and simple graph.For a graph G,we use V(G)and E(G)(or V and E)to denote its vertex set and edge set,respectively.A proper k-coloring of a graph G is an assignment ?:V?{1,2,...,k} such that for any edge xy ?E,we have that?(x)??(y).We say that G is k-colorable if there exists a proper k-coloring of G.The chromatic number,denoted by x(g),of a graph G is the smallest positive integer k such that G is k-colorable.Given a list assignment L={L(v)|v?V}.If G has a proper coloring ? such that ?(v)?L(v)for each vertex v,then we say that G is L-colorable.The graph G is k-choosable if it is L-colorable for every assignment L satisfying that |L(v)|?k for all vertices v?V.The list chromatic number of G,denoted by the smallest positive integer k such that G is k-choosable.The concept of list-coloring was introduced by Vizing and independently by Erdos et al.In 1994,Thomassen proved that every planar graph is 5-choosable,whereas Voigt first presented an example of a planar graph which is not 4-choosable.The currently known smallest example of a planar graph,with 63 vertices,that is not 4-choosable was constructed by Mirzakhani in 1996.Moreover,Gutner investigated that determining whether a planar graph is 4-choosable is NP-hard.Recently,the research of 4-choosable of planar graphs attracts much more attention around the world.In this master thesis,we shall investigate this problem and give several sufficient conditions for planar graphs to be 4-choosable.In Chapter 1,we introduce some definit ions and a brief survey of list-coloring.In Chapter 2 and Chapter 3,we make use of contradiction to show that the minimal counterexample cannot exist.The main methods are the coloring extension and the classical discharing.More precisely,we shall prove the following two results:(1)If every 5-cycle of toroidal graph G is not adjacent simultaneously to 3-cycle and 4-cycle,then G is 4-choosable.(2)If G is a planar graph so that each vertex is not incident with 3-,4-,5-,6-cycles simultaneously,then G is 4-choosable.In Chapter 4,we investigate the structures of maximal planar graph with diameter at most two and minimum degree 4.Then we prove the following result(3)Each planar graph of diameter at most two is 4-choosable.