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.

05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
PDF BibTeX Cite
Full Text: DOI