zbMATH — the first resource for mathematics

Total colorings of planar graphs with large maximum degree. (English) Zbl 0883.05053
The authors prove that for any planar graph \(G\) with maximum degree \(\Delta\geq 11\), its total chromatic number \(\chi_T(G)= \Delta+1\). This result improves an earlier result due to the same authors. The proof begins by finding some “reducible configurations” of a minimum counterexample \(G=(V,E)\) (a counterexample with \(|V|+|E|\) minimum) and then using “discharging” to obtain a contradiction.

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
PDF BibTeX Cite
Full Text: DOI