Chromatic numbers of quadrangulations on closed surfaces

It has been shown that every quadrangulation on any nonspherical orientable closed surface with a sufficiently large representativity has chromatic nu mber at most 3. In this paper, we show that a quadrangulation G on a nonori entable 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, we characterize the quadrangulations on the torus and the Klein bottle with c hromatic number exactly 3. By our characterization, we prove that every qua drangulation on the torus with representativity at least 9 has chromatic nu mber at most 3, and that a quadrangulation on the Klein bottle with represe ntativity 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 of our theory, we prove that every nonorientable closed surface N-k admits an eul erian triangulation with chromatic number at least 5 which has arbitrarily large representativity. (C) 2001 John Wiley & Sons, Inc. J Graph Theory 37: 100-114, 2001.