Is there always a complete graph of maximum chromatic number?

Question

The Four Colour Theorem states that the maximum chromatic number of a planar graph is four. The upper bound is achieved by $K_4$. Two ways to generalise this theorem which can be combined are to consider graphs on other surfaces, or to consider maps with regions having a bounded number of contiguous parts, or, more precisely, partitioning the vertices $V$ of the graph into sets $S$ with each $|S|<n$ for some $n\in\mathbb{N}$, containing no adjacent members and colouring the sets so that if $S$ contains $v$ adjacent to $w$ in $T$, then $S$ and $T$ have different colours. In these generalisations there is always an upper bound. In each example I am aware of: the torus, the Mobius band, and maps in the plane with regions having at most two non-contiguous parts, the upper bounds are also achieved by complete graphs, respectively $K_7$, $K_6$ and $K_{12}$. Are there known examples where the upper bound is not achieved by a complete graph?

Answer 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.