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.

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