A Problem On Polychromatic Colorings Of Some Plane Graphs

Plane graph is a class of graph which can be drawn in the plane so that its edges meet only at their common ends.In the paper,we only study simple plane graph.Simple graph has no multi-edges or loops.Let G=(V(G),E(G),F(G))be a plane graph with vertex set V(G),edge set E(G),face set F(G),respectively.For f ? F(G),the size of face f is the number of vertices on its boundary,denoted by g(f).For a plane graph G,let g(G)denote the smallest size of the faces in G.Let{1,…,k} be a color set.A vertex k-coloring of G is a map ?:V(G)?{1,…,k}.We say that a face f?F(G)is k-polychromatic if all k colors appear on the ver-tices of f.A vertex k-coloring of G is called k-polychromatic if every face(also the outer-face)of G is k-polychromatic.The polychromatic number of G,denoted by p(G),is the largest number k such that there is a k-polychromatic coloring of G.Let p(g)=min{p(G)|G is plane graph with g(G)=g}.which is the infimum of the polychromatic numbers of plane graphs G with g{G)=g.Firstly,we define simplified dual graph H(G)of plane graph G.H(G)is also a plane graph.The vertex set of H(G)is F(G).If two faces in G have common 2-vertices,their corresponding vertices in H(G)are adjacent.If we give a new col-or to a 2-vertex,both two incident faces get the new color meanwhile.Our work extends Alon's result that p(g)?(?)3g-5/4? We discuss three classes of special plane graphs,of which simplified dual graphs are odd cycles,even cycles or stars.By virtue of edge cover decomposition of H,we can improve lower bound of p(g)from(?)3g-5/4? to(?)3g-5+w/4?for an integer w?0.When w>0,we extend a result of Alon et al.Secondly,for general simple plane graphs,we discuss their polychromatic col-orings according to the edge cover decomposition of their simplified dual graph.For any simple plane graph,minimum degree is at most 5.A result due to Gupta says that every simple graph G can be partitioned into s disjoint edge cover,where?(G)-1?s??(G).We can improve lower bound of p(g)from(?)3g-5/4? to(?)3g-5/sw/4?for an integer w?0.The thesis consists of four chapters.In Chapter 1,we mainly introduce the background and significance of polychromatic colorings of graphs,give some basic concepts and symbols to be used in this thesis,and give our main results.In Chap-ter 2.we study polychromatic colorings of three special classes of plane graphs.In Chapter 3,discuss polychromatic colorings of general plane graphs and extend a previous result.In Chapter 4,we give some problems for further research.