Coloring Eulerian triangulations of the projective plane (Q1349103)

Let \(G\) be an Eulerian triangulation of the projective plane. In this paper it is shown that \(\chi (G)\leq 5\) and \(G\) has a color factor. Moreover, if \(U\) is any color factor of \(G\), then (i) \(\chi (G)=3\) if and only if \(G-U\) is bipartite; (ii) \(\chi (G)=4\) if and only if \(G-U\) is not bipartite and does not contain a quadrangulation of the projective plane; and (iii) \(\chi (G)=5\) if and only if \(G-U\) is not bipartite and contains a quadrangulation of the projective plane. Such a quadrangulation is necessarily nonbipartite. As a corollary it is deduced that there is a polynomial time algorithm to compute the chromatic number of Eulerian triangulations of the projective plane.