A Grunbaum coloring of a triangulation G on a surface is a 3-edge coloring of G such that each face of G receives three distinct colors on its boundary edges. In this paper, we prove that every Fisk triangulation on the projective plane P has a Grunbaum coloring, where a "Fisk triangulation" is one with exactly two odd degree vertices such that the two odd vertices are adjacent. To prove the theorem, we establish a generating theorem for Fisk triangulations on P. Moreover, we show that a triangulation G on IF has a Grunbaum coloring with each color-induced subgraph connected if and only if every vertex of G has even degree. (C) 2016 Elsevier B.V. All rights reserved.
展开▼
