Extension to 3-Colorable Triangulations
Atsuhiro Nakamoto, Kenta Noguchi, Kenta Ozeki · SIAM Journal on Discrete Mathematics · 2019
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.