Chromatic numbers of quadrangulations on closed surfaces (Q2744570)

\textit{J. P. Hutchinson} [Three-coloring graphs embedded on surfaces with all faces even-sided, J. Comb. Theory, Ser. B 65, No. 1, 139-155 (1995; Zbl 0828.05029)] proved that every quadrangulation of an orientable closed surface with a sufficiently large face-width has chromatic number at most 3. In this paper, it is shown that a quadrangulation \(G\) of a nonorientable closed surface \(N_k\) has chromatic number at least 4 if \(G\) has a cycle of odd length which cuts open \(N_k\) into an orientable surface. Moreover, quadrangulations on the torus and the Klein bottle with chromatic number exactly 3 are characterized. It is proved that every quadrangulation of the torus with face-width at least 9 has chromatic number at most 3, and that a quadrangulation of the Klein bottle with face-width at least 7 has chromatic number at most 3 if a cycle cutting open the Klein bottle into an annulus has even length. As an application it is proved that every nonorientable closed surface admits an Eulerian triangulation with chromatic number 5 which has arbitrarily large face-width. The main result of this paper has been extended by Seymour and the reviewer [Coloring locally bipartite graphs on surfaces, J. Comb. Theory, Ser. B (2002), in print] who also proved the converse statement: A graph \(G\) embedded into a nonorientable surface with large face-width and with an even cycle cutting the surface open into an orientable surface has chromatic number at most 3. Moreover, if \(G\) does not contain a quadrangulation of the same surface as a subgraph, the chromatic number is at most 3 also when cycles cutting nonorientability have odd length. In particular, quadrangulations treated in the paper under review are 4-critical if every 4-cycle is facial. A special case of this extension has been obtained independently by \textit{A. Nakamoto, S. Negami}, and \textit{K. Ota} [Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces, preprint, 2001].