# zbMATH — the first resource for mathematics

On the total coloring of planar graphs. (English) Zbl 0653.05029
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
Full Text: