×

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
PDF BibTeX Cite
Full Text: DOI