8
$\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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Everything is $2$-dimensional here? $\endgroup$
    – Sam Hopkins
    Commented Jun 23, 2021 at 22:51
  • 1
    $\begingroup$ Yes, but one can formulate the question in higher dimensions. $\endgroup$
    – Hailong Dao
    Commented Jun 23, 2021 at 22:53
  • 6
    $\begingroup$ Each vertex should have even degree (this is necessary and sufficient for 2-dimensional sphere.) $\endgroup$
    – Fedor Petrov
    Commented Jun 23, 2021 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
    Commented Jun 23, 2021 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
    Commented Jun 23, 2021 at 23:59

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think we posted essentially the same explanation at the same time... $\endgroup$
    – Sam Hopkins
    Commented Jun 24, 2021 at 0:01
  • $\begingroup$ Just noticed that. I upvoted your comment! $\endgroup$
    – Tony Huynh
    Commented Jun 24, 2021 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
    Commented Jun 24, 2021 at 0:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .