Nonrevisiting cycles on surfaces Original Research Article

A polyhedral map on a surface is a 2-cell embedding of a connected graph on the surface such that the intersection of any two faces of the map is either empty, a single vertex, or a single edge. For a polyhedral map M, the question of the existence of a nonplanar cycle whose intersection with every face of M is either connected or empty (such a cycle is said to be nonrevisiting), remains open. The only surfaces that are known to have such cycles are the projective plane, torus, and Klein bottle (Barnette, Discrete Math. 70 (1988) 1–16). This paper uses the notion of a polygonal representation of a polyhedral map to extend the result in Barnette (1988) to a class of polyhedral maps on the double torus and connected sum of three projective planes. In this regard, a graph coloring conjecture is proposed and is shown to be true for K3, 3 and all planar graphs.