Coloring vertices and faces of maps on surfaces (Q708418): Difference between revisions

\textit{A map on a surface} is a cellular embedding of a graph (possibly with loops and multiedges) in the surface. The vertex-face chromatic number \(\chi_{vf} (M)\) of a map \(M\) on a surface is the minimum integer \(m\) such that the vertices and faces of \(M\) can be coloured by \(m\) colours in such a way that adjacent or incident elements receive distinct colours. The vertex-face chromatic number \(\chi_{vf} (S)\) of a surface \(S\) is the maximal value of \(\chi_{vf} (M)\) taken over all maps \(M\) on \(S\). The author provides an upper on \(\chi_{vf} (S)\) for the surfaces of Euler genus \(\geq 2\). The upper bound is less (by 1) than Ringel's upper bound on the 1-chromatic number of a surface for about 5/12 of all surfaces (see [\textit{G. Ringel}, ``A nine color theorem for the torus and the Klein bottle,'' The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 507--515 (1981; Zbl 0469.05031)]). The author presents some arguments that indicate that the upper bound on the vertex-face chromatic number is tight.