Abstract. We completely characterize the triangulations of the projective plane that admit a spanning bipartite quadrangulation subgraph. This is an affirmative answer to a question by Kündgen and Ramamurthi [ J. Combin. Theory Ser. B, 85 (2002), pp. 307–337] for the projective planar case.

We show that every bipartite planar graph with minimum degree at least 3 has proper orientation number at most 3.

In order to attack some problems in computational geometry, Hoffmann and Kriegel [ SIAM J. Discrete Math., 9 (1996), pp. 210--224] considered the problem of whether a plane map can be extended to a 3-colorable triangulation by adding edges. In this paper, we improve their results to maps on nonspherical surfaces, by showing the following two results for a mosaic, that is, a map on a surface each of whose faces is triangular or quadrangular: a necessary and sufficient condition for mosaics on a surface to be extended to a 3-colorable triangulation (Theorem 5) and an explicit formula for calculating the number of distinct 3-colorable triangulations extended from a given mosaic on a surface (Theorem 6). These results suggest a significant gap between the planar case and the nonspherical case. We also show that they improve several known results and have an application to a polychromatic coloring.

Extension of a graph $G$ is the construction of a new graph with certain properties by adding edges to some pairs of vertices in $G$. In this paper, we focus on extension of a quadrangulation of a surface to even triangulations, where a quadrangulation is a map on a surface with every face quadrangular and a triangulation is even if all the vertices have even degree. Zhang and He [SIAM J. Comput., 34 (2005), pp. 683--696] gave a formula for the exact number of distinct even triangulations extended from a given plane quadrangulation, and a lower bound of the number for the case of orientable nonspherical surfaces. They also posed the problem of finding the exact number for the latter case. In this paper, using topological methods, we improve the results by Zhang and He in the following directions: (I) extension of quadrangulations of a nonorientable surface and (II) complete enumeration of even triangulations extended from a given quadrangulation of a nonspherical surface. Indeed, we completely solve the problem by Zhang and He.