\(N\)-flips in even triangulations on the projective plane (Q998424)

A triangulation \(G\) of a closed surface \(F^2\) is a simple graph (with no loops and no multiple edge) embedded on the surface so that each face is triangular. A triangulation \(G\) is \textit{even} if each vertex of \(G\) has even degree. Let \(G\) be an even triangulation. {\parindent=6mm \begin{itemize}\item[(i)]Assume that \(G\) has hexagonal region \(v_1v_2v_3v_4v_5v_6\) with diagonals \(v_1v_3\), \(v_3v_6\) and \(v_4v_6\) and no inner vertices. The \(N\)--\textit{flip} of the path \(v_1v_3v_6v_4\) is the operation of replacing the diagonals \(v_1v_3\), \(v_3v_6\) and \(v_4v_6\) with \(v_1v_5\), \(v_2v_5\) and \(v_2v_4\) in the hexagonal region. An \(N\)--flip obviously transforms an even triangulation into an even triangulation. \item[(ii)]If \(G\) is on a closed surface, let \(v\) be a vertex of \(G\) with its link \(v_1{} \ldots v_k\). Put two vertices \(x\) and \(y\) on \(v v_1\) and join them to \(v_2\) and \(v_k\), and let \(G'\) be the resulting graph. The \(P_2\)--\textit{flip} of \(\{x, y\}\) is the operation of moving the inserted vertices \(x\) and \(y\) to the edge \(v v_2\) and joining them to \(v_1\) and \(v_3\). \end{itemize}} This operation preserves the simpleness of the graph, and if \(G\) is \(3\)--colored, a \(P_2\)--flip changes its tripartition. In the paper under review, the authors show that any two even triangulation \(G\) and \(G'\) on the projective plane with \(| V(G)| = | V(G')| \geq 14\) can be transformed into each other by the two operations \(N\)--flip and \(P_2\)--flip, if and only if both of them are simultaneously \(3\)--colorable, or not.