×

zbMATH — the first resource for mathematics

A structural theorem on planar graphs and its application to coloring. (Russian) Zbl 0760.05034
Let \(G\) be a planar graph with maximum degree \(\Delta(G)\). \(\chi_{vef}(G)\) denotes the minimum number of colours which are needed for colouring the vertices, edges and faces of \(G\) such that any two incident or adjacent elements receive different colours. The author proves that \(\Delta(G)\geq 8\) implies \(\chi_{vef}(G)\leq\Delta+4\). Moreover, a structural theorem on planar graphs is obtained and its applications to colouring problems are discussed.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite