# When is a triangulation of sphere two-colorable?

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.

• Everything is $2$-dimensional here? – Sam Hopkins Jun 23 at 22:51
• Yes, but one can formulate the question in higher dimensions. – Hailong Dao Jun 23 at 22:53
• Each vertex should have even degree (this is necessary and sufficient for 2-dimensional sphere.) – Fedor Petrov Jun 23 at 23:05
• @FedorPetrov: that sounds reasonable. Is there a reference, and if not, would you mind giving a full answer? Thanks. – Hailong Dao Jun 23 at 23:42
• @HailongDao: consider the planar dual graph. The condition of the primal graph having each vertex of even degree is the same as each face of the dual graph having an even number of edges. It is a small exercise to show that for planar graphs this implies that every cycle has even length, which is well-known to be equivalent to the graph being bipartite (i.e., vertex 2-colorable). – Sam Hopkins Jun 23 at 23:59

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.