A friend and I were reading up on the classification of compact surfaces when we realized that the minimal number of triangles in a triangulation of the sphere, torus, and projective plane are 4 (routine), 7 (an exercise in several places, such as in Katok - Lectures on Surfaces), and 6 (using a similar counting trick as the torus) respectively. This was strange as we knew the chromatic numbers of the plane, torus, and projective plane to also be 4 (the Four-Color Theorem), 7 (folklore), and 6 (http://mathworld.wolfram.com/ProjectivePlane.html) respectively.

Question: What is known about the relationship between these two invariants?

I did a little research and I think I kind of see what is going on. I'll outline what I know here, though I hope an expert will help fill in the details or give further directions: I think the relevant result is Heawood's conjecture (apparently not a conjecture), which gives a formula for the chromatic number of any surface (apparently except the Klein bottle) given the genus. In particular, there exist triangulations of the given numbers in the above three situations, so they match. If this assessment is correct, then my question above basically becomes something like:

Question: is it obvious that when there exists a map that requires the prescribed number of colors given by Heawood's not-so-Conjecture, then there exists a triangulation with the same chromatic number? (bonus: can we force the triangulation to be a refinement of the map?)

  • $\begingroup$ For dummies: I heard about chromatic number for graphs, what is chromatic number for surfaces ? $\endgroup$ – Alexander Chervov Jan 29 '13 at 5:34
  • 1
    $\begingroup$ @Alexander, it's the maximum chromatic number for a graph embedded in the surface. $\endgroup$ – Gerry Myerson Jan 29 '13 at 6:34
  • $\begingroup$ Hmm. Why can't I take a non-triangular embedding and triangularize it? It seems to enforce strictly more conditions on adjacency and so should preserve chromatic number (at least in the right direction). I thought I found a nuance for this when I first thought about hte problem, now I don't see it anymore. $\endgroup$ – Yan X Zhang Jan 30 '13 at 4:39
  • $\begingroup$ @Gerry Thank you ! Is there reason why "that maximum" is not infinity ? Sorry if my question is stupid $\endgroup$ – Alexander Chervov Jan 30 '13 at 9:36

The answer to your "is it obvious" is "no". But it is a theorem in many cases. Wikipedia + one click takes to you "Solution of the Heawood map coloring problem" by Ringel and Youngs. There they completed the proof that Heawood's bound on the chromatic number was tight for surfaces with positive genus. As they explain in their introduction, they do this by producing an embedding of a complete graph in each case. The embedding for $K_N$ is triangular if $N$ is congruent to 0, 3, 4, or 7 mod 12.

To see this, note that Ringels and Young show that if $\gamma=\lceil (n-3)(n-4)/12\rceil$, then there is an embedding of $K_n$ in the surface of genus $\gamma$, whence the chromatic number of the surface is at least $n$. By Euler's formula $n-e+f=2-2g$ and for $K_n$ we have $e=n(n-1)/2$ and $3f \le 2e$ (with equality if and only if each face is a triangle). Hence $$ -n(n-7)/6 \ge 2-2g $$ or equivalently $g \le (n-3)(n-4)/12$. So in the mod 12 cases listed the embedding is triangular.

  • $\begingroup$ Thanks Chris! Can you tell me exactly where they say it is triangular? I actually did look up that paper and searched through it for mention of triangularization and couldn't find it. $\endgroup$ – Yan X Zhang Jan 29 '13 at 17:29
  • $\begingroup$ @yanzhang I am sorry, I goofed. The embedding is only triangular in certain cases, as noted in my revised answer. $\endgroup$ – Chris Godsil Jan 29 '13 at 19:23
  • $\begingroup$ @Chris: thanks for the informative answer. $\endgroup$ – Yan X Zhang Jan 30 '13 at 4:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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