On the total coloring of planar graphs. (English) Zbl 0653.05029

Borodin, O. V.

J. Reine Angew. Math. 394, 180-185 (1989).

By Behzad and Vizing’s conjecture (1968), \(\kappa_ t(G)\leq \Delta (G)+2\), where \(\kappa_ t(G)\) is the total chromatic number and \(\Delta\) (G) - the maximal degree of a graph G. For planar graphs G it is proved here that \(\kappa_ t(G)\leq \Delta (G)+2\) if \(\Delta\) (G)\(\not\in \{6,7,8\}\), \(\kappa_ t(G)\leq \Delta (G)+3\) always, and \(\kappa_ t(G)=\Delta (G)+1\) if \(\Delta\) (G)\(\geq 14\).

Reviewer: O.V.Borodin

MSC:

05C15	Coloring of graphs and hypergraphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

total chromatic number; maximal degree; planar graphs