8
$\begingroup$

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?)

$\endgroup$
4
  • $\begingroup$ For dummies: I heard about chromatic number for graphs, what is chromatic number for surfaces ? $\endgroup$ Jan 29, 2013 at 5:34
  • 1
    $\begingroup$ @Alexander, it's the maximum chromatic number for a graph embedded in the surface. $\endgroup$ Jan 29, 2013 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$ Jan 30, 2013 at 4:39
  • $\begingroup$ @Gerry Thank you ! Is there reason why "that maximum" is not infinity ? Sorry if my question is stupid $\endgroup$ Jan 30, 2013 at 9:36

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Jan 29, 2013 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$ Jan 29, 2013 at 19:23
  • $\begingroup$ @Chris: thanks for the informative answer. $\endgroup$ Jan 30, 2013 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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