Coloring Problem Of Planar Graph

The edge-face chromatic number xef(G) of a planar graph G is the minimal number of colors needed for coloring the edges and faces of G such that no two adjacent or incident elements receive the same color. The entire chromatic number xvef (G) of a planar graph G is the minimal number of colors needed for coloring the vertices, edges and faces of G such that no two adjacent or incident elements receive the same color.Let G = (V,E) be a planar graph, if there is a outer edge e E, such that G-e is a outerplanar graph (that is, all vertices of G - e are incident with outer face), then G is an almost outerplanar graph. In this paper, based on the further properties of outerplanar graphs, we investigate the problems of the edge-face coloring and entire coloring on almost outerplanar graphs. We show that for any almost planar graph G, the edge-face chromatic number of G must satisfy xef (G) max{7,A(G) + 1}, moreover, xef (G) = A(G) when G is 2-connected and (G) 6 ; the entire chromatic number must satisfy xvcf(G) max{9, (G)+2} , and xvef(G) = (G) + 1 when G is 2-connected and (G) 7 .