Kempe equivalence of 4-colorings of graphs on non-orientable surfaces

Two vertex colorings of a graph are Kempe equivalent if they can be transformed into each other by a sequence of Kempe changes which interchange the colors used on a component of the subgraph induced by two color classes. Fisk showed that every two vertex 4-colorings of a 3-colorable triangulation on the sphere are Kempe equivalent, and then Mohar extended this result to any 3-colorable planar graph. Fisk also verified that there are 4-chromatic triangulations on the sphere and 3-colorable triangulations on the torus such that some two 4-colorings of them are not Kempe equivalent. In this paper, we show that every two vertex 4-colorings of a 3-colorable triangulation on the projective plane or the Klein bottle are Kempe equivalent. Our result is best possible in terms of all conditions; 3-colorability, the genus of a non-orientable surface, a triangulation (i.e., it cannot be replaced with a graph).