Weakly Edge-face Coloring Of Plane Graphs

Let G =(V,E,F)be a connected,loopless plane graph,with vertex set V and edge set E,and face set F.And edge-face k-coloring of a plane graph G is an assignment?:E(G)? F(G)? {1,2,…,k} such that ?(e1)? ?(e2)if an edge e1 is adjacent to'an edge e2;?(f1)??(f2)if a face f1 is adjacent to a face f2;?(e)??(f)if an edge e is incident to a face f.The edge-face chromatic number of G,denoted 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.Motivated by forcing the edge-face coloring of plane graph,in 2016,Fabrici et.al firstly introduced the concept of weakly edge-face coloring.A plane graph G is called weakly edge-face k-colorable if there is a mapping ?:E(G)? F(G)? {1,2,…,k} such that any two incident elements,adjacent faces,and facially adjacent edges receive distinct colors.Here,e1 and e2 are called facially adjacent if e1 and e2 are consecutively adjacent with the same face.The weakly edge-face chromatic number of G,denoted by xef(G),is defined to be the smallest integer k such that G has a weakly edge-face k-coloring.In 2016,Fabrici proved that every connected,loopless,bridgeless plane graph is weak-ly edge-face 6-colorable.In addition,Fabrici conjectured that every connected,loopless,bridgeless plane graph is weakly edge-face 5-colorable.This conjecture has attracted much attention.However,this conjecture is still widely open.In this master thesis,we shall mainly investigate weakly edge-face coloring of planar graphs.In Chapter 1,we first collect some basic notations that will be used frequently throughout the thesis.Then we present a chief survey in this direction and later we state the main results obtained.In Chapter 2,Chapter 3 and Chapter 4,we shall use mathematical induction method to prove that Halin graphs,plane triangulations and outerplanar graphs satisfy the above conjecture.More precisely,we will show that:(1)Every Halin graph is weakly edge-face 5-colorable.(2)Every plane triangulation is weakly edge-face 5-colorable.(3)Every outerplanar graph is weakly edge-face 5-colorable.We should point out that the upper bound 5 is always tight in above mentioned results.