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