Every Plane Graph of Maximum Degree 8 has an Edge-Face 9-Coloring
Ross J. Kang, Jean-Sébastien Sereni, Matěj Stehlík · SIAM Journal on Discrete Mathematics · 2011
An edge-face coloring of a plane graph with edge set [Formula: see text] and face set [Formula: see text] is a coloring of the elements of [Formula: see text] such that adjacent or incident elements receive different colors. Borodin [2 2 ] proved that every plane graph of maximum degree [Formula: see text] can be edge-face colored with [Formula: see text] colors. Borodin’s bound was recently extended to the case where [Formula: see text]. In this paper, we extend it to the case [Formula: see text].