7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Everything is $2$-dimensional here? $\endgroup$ – Sam Hopkins Jun 23 at 22:51
  • 1
    $\begingroup$ Yes, but one can formulate the question in higher dimensions. $\endgroup$ – Hailong Dao Jun 23 at 22:53
  • 6
    $\begingroup$ Each vertex should have even degree (this is necessary and sufficient for 2-dimensional sphere.) $\endgroup$ – Fedor Petrov Jun 23 at 23:05
  • 3
    $\begingroup$ @FedorPetrov: that sounds reasonable. Is there a reference, and if not, would you mind giving a full answer? Thanks. $\endgroup$ – Hailong Dao Jun 23 at 23:42
  • 5
    $\begingroup$ @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). $\endgroup$ – Sam Hopkins Jun 23 at 23:59
11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I think we posted essentially the same explanation at the same time... $\endgroup$ – Sam Hopkins Jun 24 at 0:01
  • $\begingroup$ Just noticed that. I upvoted your comment! $\endgroup$ – Tony Huynh Jun 24 at 0:19
  • 1
    $\begingroup$ Haha, sorry, wasn't fishing for upvotes. Just wanted to point out that this is a very well-known equivalence for 2-colorability of (the faces of) a planar map... I give it as homework in an undergrad combinatorics class. But not sure of specific reference/attribution. $\endgroup$ – Sam Hopkins Jun 24 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.