Let $T$ be a triangulation of sphere. We say that $T$ is $k$-colorable if the triangles of $T$ can be assigned with $k$ colors such that any two triangles with a common edge have different colors.


I am interested in $2$-colorable triangulations. Easy examples are boundaries of bipyramids over even polygons such as the simplicial comlex $\{123,134,145,152, 623,634,645,652\}$


**Question**: Are there efficient criteria to tell if a triangulation is $2$-colorable? How to construct $2$-colorable triangulations? Do they arise in some contexts?


I am also interested in triangulations of other manifolds, so any such references are welcome.



When is a triangulation of sphere two-colorable?
As Fedor Petrov mentions in the comments, a necessary and sufficient condition is that each vertex has even degree. Here is a proof.


Let $T^\*$ be the dual graph of the triangulation. That is, the vertices of $T$ are the faces of the triangulation, and two faces are adjacent if they share an edge. Rephrased, your question is asking when $T^\*$ is bipartite. So, it suffices to prove that a planar graph $G$ is bipartite if and only if the dual graph $G^\*$ is Eulerian (all vertices have even degree). For one direction, if $G$ is bipartite, then all cycles of $G$ are even. In particular, all facial cycles are even, and hence $G^\*$ is Eulerian. For the other direction, suppose that the dual graph $G^\*$ is Eulerian. Thus, each face of $G$ is even. Since the cycle space of $G$ is generated by the facial cycles of $G$ (take the symmetric difference of all faces inside the cycle), this implies that *every* cycle of $G$ is even. Hence $G$ is bipartite.


