Edge‐face chromatic number and edge chromatic number of simple plane graphs
Rong Luo, Cun‐Quan Zhang · Journal of Graph Theory · 2005
Abstract Given a simple plane graph G, an edge‐face k‐coloring of G is a function ϕ : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ϕ(a) ≠ ϕ(b). Let χe(G), χef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χef(G) = χe(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory