Face 2-colourable triangular embeddings of complete graphs (Q1272468): Difference between revisions

Face 2-colorable triangulations of orientable surfaces by complete graphs \(K_n\) exist if and only if \(n\equiv 3\) or \(7\pmod{12}\). The necessity follows from the Euler identity for 2-cell imbeddings and parity considerations. The sufficiency comes from current-graph constructions used in proving the Heawood map-coloring theorem. (Such imbeddings determine pairs of Steiner triple systems in a natural manner.) The present authors give an alternative construction for half of the residue class \(n\equiv 7\pmod{12}\), using surgery and voltage-graph lifting to extend a face 2-colorable triangulation for \(K_m\) to one for \(K_{3m-2}\). They also note the existence of nonisomorphic orientable imbeddings of \(K_n\) for \(n= 12s+7\), \(s>0\); one imbedding is 2-face-colorable, the other not, for each such \(s\). This compares with work by \textit{S. Lawrencenko}, \textit{S. Negami} and the reviewer [Discrete Math. 135, No. 1-3, 367-369 (1994; Zbl 0823.05027)], finding three nonisomorphic triangulations for \(K_{19}\). A development in the present paper similar to that for the orientable case finds nonisomorphic nonorientable triangulations for \(K_n\), for half of the residue class \(n\equiv 1\pmod 6\).