Total colorings of planar graphs with large maximum degree. (English) Zbl 0883.05053

Borodin, O. V.; Kostochka, A. V.; Woodall, D. R.

J. Graph Theory 26, No. 1, 53-59 (1997).

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.

Reviewer: H.P.Yap (Singapore)

MSC:

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

Keywords:

planar graph; maximum degree; total chromatic number