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



coincidence between minimal triangulation numbers and chromatic numbers
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.


