Facial(List)Edge-face Coloring And Facial Entire Coloring Of Plane Graphs

All graphs considered in this paper are connected and loopless.Let G=(V,E,F)be a plane graph,with vertex set V,edge set E,and face set F.A plane graph G is edge-face k-colorable if there is a mapping ?:E(G)?F(G)?{1,2,…,k} such that any two adjacent edges e1,e2,satisfying ?(e1)??(e2);any adjacent faces f1,f2,satisfying?(f1)??(f2);and any incident edges and faces e,f,satisfying ?(e)??(f).The edge-face chromatic number of G,denoted by Xef(G)is defined to be the least integer k such that G has an edge-face k-coloring.This notion was first independently studied by Jucovic and Fiamcik in 1970Inspired by edge-face coloring of planar graphs,Kronk and Mitchem introduced the entire coloring of plane graph in 1973.A plane graph G is entire k-colorable if there exists a mapping ?:V(G)?E(G)?F(G)?{1,2,…,k,}such that any two adjacent vertices v1,v2,satisfying ?(v1)??(v2);any two adjacent edges e1,e2,satisfying ?(e1)??(e2);any adjacent faces f1,f2,satisfying ?(f1)??(f2);and any incident vertices,edges and faces v,e,f,satisfying ?(v)??(e),?(v)??(f),?(e)??(f).The entire chromatic number of G,denoted by ?vef(G)is defined to be the least integer k such that G has an entire k-coloring.Motivated by the edge-face coloring of planar graphs,in 2016,Fabrici et al.firstly introduced the concept of facial edge-face coloring and facial entire coloring.Here,e1 and e2 are called facially adjacent if e1 and e2 are consecutively adjacent with the same face.A facial edge-face k-coloring of G is a mapping ?:E(G)?F(G)?(1,2,…,k}such that any two facially adjacent edges,adjacent faces,and incident edge and face have distinct colors.The facial edge-face chromatic number of G,denoted by Xef(G),is defined to be the least integer k such that G has a facial edge-face k-coloringIn 2016,Fabrici,Jendrol'and Vrbjarova proved that ?ef(G)?6 for any connected,loopless and bridgeless plane graph G.Moreover,they conjectured that every connected,loopless and bridgeless plane graph is facially edge-face 5-colorableA facial entire k-coloring of G is a mapping ?:V(G)?E(G)?F(G)?{1,2,…,k}such that any two adjacent vertices,facially adjacent edges,adjacent faces,and incident edge and face receive distinct colors.The facial entire chromatic number of G,denoted by ?vef(G),is defined to be the least integer k such that G has a facial entire k-coloringFabrici,Jendrol'and Vrbjarova showed us that Xvef(G)<8 for any connected,loopless and bridgeless plane graph G.They also proposed a conjecture which states that every connected,loopless and bridgeless plane graph is facially edge-face 7-colorableThe above two conjectures have attracted much attention,and so far these two conjectures are still widely open.This thesis mainly focuses on the above two conjectures In other words,we mainly investigate facial edge-face coloring and facial entire coloring of planar graphsIn Chapter 1,we firstly collect some basic concepts of graph theory that will be used in the thesis.Then we briefly summarize the research progress relating related fields,and finally the main results will be presentedIn Chapters 2 and 4,by using mathematical induction methods,we focus on facial edge-face coloring and facial entire coloring of K4-minor-free graphs.Besides,we shall apply coloring extending techniques and algebra methods to obtain the following results(1)Every K4-minor-free graph is facially edge-face 5-colorable(2)Every K4-minor-free graph is facially entire 7-colorableIn Chapter 3,we will study facial list edge-face coloring of graphs.More precisely,we prove the following(3)Every maximal planar graph is facially edge-face 5-choosableIt is worthy to pointing out that our first and the third result are both tight in sense that there exist a K4-minor-free graph and a maximal planar graph whose facial edge-face chromatic number is exact 5.