Edge-face Coloring And Edge-face List Coloring Of Plane Graphs

Let G=(V.E,F)be a connected,loopless plane graph,with vertex set V,edge set E,and face set F.A plane graph G is edge-face k-colorable if the elements of E(G)U F(G)can be colored with k colors such that any two adjacent or incident elements receive different colors.The edge-face chromatic number of denoted by Xef(G)is the smallest integer k such that G is edge-face k-colorable.This notion was first independently studied by Jucovic and Fiamcik in 1970.Erdos and Vizing independently proposed the concept of list coloring in the 1960s A graph G is edge-face L-colorable if for a given list assignment L={L(x):x?E(G)?F(G)} there is an edge-face coloring ? such that ?(x)?L(x),for x?E(G)?F(G).If G is edge-face L-colorable for any list assignment L with |L(x)|?k for all x?E(G)?F(G),then G is edge-face k-choosable.The edge-face list chromatic number Xefl(G)of G is the smallest integer k such that G is edge-face k-choosable.In this thesis,we study the edge-face coloring and the edge-face list coloring of planar garphs.It consists of three chapters as follows.In Chapter 1,we first collect some basic notations that will be used throughout the thesis,and resume the research status of edge-face coloring and edge-face list coloring of planar graphs.Then we state the main results obtained in this master thesis.In Chapter 2,we characterize the edge-face list chromatic number of wheel graphs by using the famous Combinatorial Nullstellcnsatz.Then we obtain an upper bound of the edge-face choosability of Halin graph with given maximum degree.In Chapter 3,we investigate the edge-face coloring of plane graphs.In 2001,Sanders and Zhao proposed a conjecture which states that every plane graph G with ??3 is edge-face(?+2)-colorable.They confirmed it for the cases ??3 and ??7.Later,Chen,Raspaud and Wang settled the case ??6 for this conjecture in 2014.In this chapter,we give a positive answer for the case that ?=5.That is,we prove that every plane graphs with ??5 is edge-face 7-colorable.