STRUCTURAL THEOREM ON PLANE GRAPHS WITH APPLICATION TO THE ENTIRE COLORING NUMBER

In 1973, Kronk and Mitchem (Discrete Math. (5) 255-260) conjectured th at 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 a ny two adjacent or incident elements receive distinct colors. They suc ceeded in verifying this for D(G) = 3. A structural theorem on plane g raphs is proved in the present paper which implies the validity of thi s conjecture for all D(G) greater than or equal to 7. (C) 1996 John Wi ley & Sons, Inc.