Planar Graphs with $\Delta\ge 9$ are Entirely $(\Delta+2)$-Colorable
Yiqiao Wang, Xiaoxue Hu, Weifan Wang · SIAM Journal on Discrete Mathematics · 2014
A plane graph $G$ is entirely $k$-colorable if $V(G)\cup E(G) \cup F(G)$ can be colored with $k$ colors such that any two adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph $G$ with maximum degree $\Delta\ge 12$ is entirely $(\Delta+2)$-colorable. In this paper, we improve this result by showing that every plane graph $G$ with $\Delta\ge 9$ is entirely $(\Delta+2)$-colorable.