Structural theorem on plane graphs with application to the entire coloring number
Oleg Veniaminovich Borodin · Journal of Graph Theory · 1996
In 1973, Kronk and Mitchem (Discrete Math. (5) 255–260) conjectured that the vertices, edges and faces of each plane graph G may be colored with D(G) + 4 colors, where D(G) is the maximum degree of G, so that any two adjacent or incident elements receive distinct colors. They succeeded in verifying this for D(G) = 3. A structural theorem on plane graphs is proved in the present paper which implies the validity of this conjecture for all D(G) ≥ 7. © 1996 John Wiley & Sons, Inc.