# zbMATH — the first resource for mathematics

Structural theorem on plane graphs with application to the entire coloring number. (English) Zbl 0863.05035
H. V. Kronk and J. Mitchem [Bull. Am. Math. Soc. 78, 799-800 (1972; Zbl 0253.05121)] conjectured that the vertices, edges and faces of every plane graph $$G$$ can be colored with $$\Delta(G) +4$$ colors $$(\Delta(G)$$ is the maximum vertex degree of $$G)$$ so that any two adjacent or incident elements receive distinct colors. Kronk and Mitchem proved their conjecture for $$\Delta(G) =3$$.
In this paper, the author first proves a structure theorem for plane graphs (whose statement is too long to be reproduced here) and then uses it to prove that the Kronk-Mitchem conjecture is true for all plane graphs $$G$$ having $$\Delta(G) \geq 7$$. This result improves some of the authors own previous results.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C75 Structural characterization of families of graphs
Full Text: