Edge Choosability And Total Choosability Of Planar Graphs

The Seven Bridges of Konigsberg,published by Euler in 1736,is consid-ered to be one of the landmarks in the history of graph theory.Since then,another important branch of discrete mathematics,graph theory,began to come into people's view.With the four-color conjecture being proposed in 1852,the study of graph coloring theory has become an important research di-rection in discrete mathematics.With the birth and development of computer,four-color conjecture has been solved.Appel and Haken did verify the theorem by computer in 1976.Since then,the computer has played an important part in the study of graph theory.At the same time,several results of graph theory came into social life and manufacturing via computers.They not only show great advantages in solving problems in communication engineering,manage-ment science,but also show extraordinary value in engineering technology and humanities.We mainly discuss list edge coloring and list total coloring of some planar graphs in this paper.The graphs considered in this paper are all non-empty,undirected and finite simple graphs.Let G=(V,E)be a simple graph,using V(G)and E(G)to denote the vertex set and edge set of G.We use dG(x),or simply d(x),to denote the degree of a vertex x in G.We use ?(G)and ?(G),to denote the maximum degree and the minimum degree of G,respectively.In this paper,we mainly study list coloring of planar graphs,especially list edge coloring and list total coloring.We say that L is an edge assignment for the graph G if it assigns a list L(e)of possible colors to each edge e of G.If G has a proper edge-coloring ? such that ?(e)? L(e)for each edge e of G,then we say that G is edge-L-colorable or ? is an edge-L-coloring of G.The graph G is edge-k-choosable if it is edge-L-colorable for every edge assignment L satisfying |L(e)|? k for all e ? E(G).The list edge chromatic number Xl'(G)of G is the smallest k such that G is edge-k-choosable.Similarly we can get the definition of list total chromatic number of G,xl"(G).Similar to the proper coloring of planar graphs,we use discharging method.After many scholars' exploration and unremitting efforts,several beautiful re-sults have been obtained.On the basis of previous results,we obtained the list coloring results of the planar graphs that met some specific conditions in this paper.Theorem 1.Let G be a planar graph without 6-cycles with two chords,if?(G)>6,then xl'(G)??(G)+1,and if ?(G)? 9,then xl'(G)? ?(G).Theorem 2.Let G be a planar graph,then xl'(G)??(G)+1,if one of the following conditions holds:(1)G without 4-cycles adjacent to a 3-cycle;(2)?(G)>6 and G contains no adjacent 4-cycles.Theorem 3.Let G be a planar graph without k-cycles,then xl'(G)=?(G),xl"(G)=?(G)+ 1,if one of the following conditions holds:(1)A(G)>9 and k=8;(2)?(G)?10 and k=9.In Chapter 1,some basic definitions and symbols in graph theory are introduced firstly.Then we introduce some basic colorings and the background,important results and latest development of list coloring.Finally,the main results of this paper are listed.In Chapter 2,we introduce the edge choosability of a planar graph G without 6-cycles with two chords,and the proof of Theorem 1 is given.In Chapter 3,we introduce the edge choosability of a planar graph G without adjacent small cycles,and then the proof of Theorem 2 is given.In Chapter 4,we introduce the edge choosability and total choosability of a planar graph G without some cycles,and then the proof of Theorem 3 is given.In Chapter 5,we put forward some unresolved problems.