On The Edge-face Coloring Of Plane Graphs

In this paper all graphs are finite, simple, undirected and plane. Let G = (V, E, F) be a plane graph with vertex set V(G), edge set E(G) and face set F(G) , respectively. Let EF(G) = E(G)∪F(G) .If uv e E(G), then u is called a neighbor of v. The degree d(v)of a vertex v is the number of neighbors of v. We use A(G)andδ(G) to denote the maximum (vertex) degree and the minimum (vertex) degree of G, respectively. An edge-face coloring of a plane graph G is a coloring of EF(G) such that no two adjacent or incident elements receive the same color. Theedge-face chromatic number, denoted byχ_ef(G), of a plane graph G is the minimal number of colors needed for an edge-face coloring of G.In 1975, Mel'nikov conjectured thatâ–³(G)≤χ_ef (G)≤△(G) + 3 for any planegraph G. Waller (independently by Sanders and Zhao) proved the conjecture by using the Four Color Theorem. In 2002, Wang and Lih proved the conjecture without using the Four Color Theorem. In 1994, Borodin proved that for any plane graph G,â–³(G)≤χ_ef(G)≤max{1 1,â–³(G) +1}. In 1995, Wang proved that for any outerplane graphG,â–³(G)≤χ_ef(G)≤max{7,â–³(G) + 1}≤andχ_ef(G) =â–³(G) if G is 2-connected andâ–³(G)≥6. In 1999, Wang and Zhang further improved Wang's result and obtained theedge-face chromatic number of outerplane graphs withâ–³(G)≥5. In 2005 and 2007, Wu and Wang extended Wang's result to series-parallel graphs and proved thatχ_ef(G) =â–³(G) if G is a 2-connected SP-graph withâ–³(G)≥5.In the paper, we prove the following results. Theorem 1. Let m(m≥6) be an integer and G is an Extended Halin graph having ,â–³(G)≤m .Then there exists an edge-face coloringσwith m colors l,2,…m, such thatσ(f_o) = 1, for any vertex v∈V(f_o), let e,e₁,e₂ be three edges incidentwith v and {e₁,e₂}(?)E(f_o),|{σ(e₁),σ(f_e1),σ(e₂),σ(f_e2)}|≥3.Corollary 2.χ_ef(G) = A(G) for any Halin graph or Extended Halin graph Ghavingâ–³(G)≥6.Theorem 3. Let m(m≥5) be an integer and G is a Halin graph havingâ–³(G)≤m. Then there exists an edge-face coloringσwith m colors 1,2,…m, such that (1)σ(f_o) = 1, (2) for any e∈E_G(f_o),{σ(e),σ(f_e)} (?) {2,3,4,5}, (3) for any vertex v∈V(f_o),let e,e₁,e₂ be three edges incident with v and {e₁,e₂} (?) E(f_o),Theorem 4. Let G be a Halin graph havingâ–³(G) = 4,thenχ_ef(G) = 5.Corollary 5. Let G be a Halin graph havingâ–³(G) = 3,then 4≤χ_ef(G)≤5.Theorem 6. Let m(m≥6) be an integer and G is a double-cycle-tree graph havingâ–³(G)≤m , then Then there exists an edge-face coloringσwith m colors 1,2,…m, such that (1)σ(f_o) =σ(f₁) = 1, and (2) for any vertex v∈V(f_o), let e,e₁,e₂ be three edges incident with v and {e₁,e₂} (?) E(f_o),Theorem 7. Suppose G is a 2-connected plane graph havingâ–³(G) = 3,thenχ_ef(G) =â–³(G) ifand only if G is a 2-connected 3-regular bipartite plane graph.