List Coloring Of Plane Graphs

All graphs considered here are finite,simple(i.e.,no loops and multi-edges) and undirected.A planar graph is a graph that can be embedded into the plane so that its edges meet only at their ends.A plane graph is any such a particular embedding of a planar graph.Let G=(V,E)be a graph,k be a positive integer. A k-coloring of G is a mappingφ:Vâ†'{1,2,...,k)such thatφ(x)≠φ(y)whenever xy∈E.G is called k-colorable if it has a k-coloring.In the definition of a k-coloring φ of a graph G,the fixed set{1,2,...,k)is called the available color set for every vertex in G.If we allow the available color set may vary,then we get the notion of list coloring.More precisely,for every vertex υ∈V,we assign a list of available colors L(Ï…),then L={L(Ï…)|υ∈υ}is called an assignment of lists of colors of G.If for every υ∈V we have |L(Ï…)|=k,then L is called a k-list-assignment of G.If for every k-list-assignment L,we can always choose a color from L(Ï…)to color v such that φ(x)≠φ(y) for every edge xy∈E,then G is said to be list k-colorable or k-choosable.Observe that we may take L(Ï…)={1,2,..,k}for every Ï…,∈V,so if G is k-choosable,then G is k-colorable.However, the opposite is generally not true.Let d1,d2,...,dk be k non-negative integers,and G=(V, E)be a graph with the sets of vertices and edges V and E,respectively.A(d1,d2,...,dk)-coloring of G is a mappingφ:Vâ†'{1,2,..,k}such that the subgraph G[Vi]has maximum degree at most di,where Vi={υ∈V|φ(Ï…)=i}.A graph G is called (d1,d2,...,dk)-colorable if it admits a(d1,d2,...dk)-coloring.A graph G is called(k,d)*-list colorable(or(k,d)* choosable)if it admits an(L,d)-coloring for every list assignment L with |L(Ï…)|≥ k for all v ∈ V. Obviously, if G is (k, d)* -choosable, then G is (k, d)* -colorable. However, the opposite is generally not true.So proper list coloring is a special case of improper list coloring and improper list coloring is an extension of proper list coloring.On the question:whether a given planar graph is 3-or 4-choosable. In 1996, Gutner [8] proved that these problems are NP-hard. Thus, sufficient conditions for a planar graph to be 3-choosable or 4-choosable are of interest. In 1999, Eaton et al. conjectured that every planar graph is (4, 1)* -choosable. Surrounding the conjecture and its related question, people exerted themselves to make related research and got a series of achievements.This paper consists of three chapters, focusing on the conjecture and question, which has improved several previous results. In the first chapter, there are some defini-tions and a brief survey of proper list coloring and improper list coloring. In the second chapter, there are three of the research results:planar graphs without short cycles and having constraints on distance between triangles are 3-choosable. In the third chap-ter, there is the proof of planar graphs without adjacent cycles of length 3,4 or 8 are (3,1)* -choosable.