Edge-face coloring of plane graphs with maximum degree nine
Jean‐Sébastien Sereni, Matěj Stehlı́k · Journal of Graph Theory · 2010
An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1–3):21–33, 1994] proved that every plane graph of maximum degree Δ⩾10 can be edge-face colored with Δ + 1 colors. We extend Borodin's result to the case where Δ = 9. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:332-346, 2011