Polychromatic 4-coloring of cubic even embeddings on the projective plane

A polychromatic   k -coloring of a map G on a surface is a k -coloring such that each face of G has all k colors on its boundary vertices. An even embedding   G on a surface is a map of a simple graph on the surface such that each face of G is bounded by a cycle of even length. In this paper, we shall prove that a cubic even embedding G on the projective plane has a polychromatic proper 4-coloring if and only if G is not isomorphic to a Mِbius ladder with an odd number of rungs. For proving the theorem, we establish a generating theorem for 3-connected Eulerian multi-triangulations on the projective plane.