Coloring Eulerian triangulations of the projective plane
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.
scientific article; zbMATH DE number 1743033