×

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
PDF BibTeX XML Cite
Full Text: DOI Crelle EuDML