Is there always a complete graph of maximum chromatic number?
Solution 1:
You might want to look at the Heawood number and Ringel-Young's Theorem articles (formerly Heawood's conjecture).
I think the Klein Bottle is the only exception where a complete graph does not attain the upper bound, from that second link above. So for all other surfaces, the largest chromatic number of any graph embeddable on that surface is attained by a complete graph.