Let $\Sigma_g$ be a surface of genus $g$. The Heawood Conjecture gives a closed formula in one variable, $\chi$ (the Euler characterstic of $\Sigma_g$), for the minimal number of of colors needed to color any graph drawn on $\Sigma_g$.
Ringel-Youngs, 1968: The Heawood Conjecture is true, except for $g=0$ (where we don't know the answer – this would be the Four-Color Conjecture) and the Klein bottle (where a graph was shown to be colorable with fewer than predicted by the formula).
Of course, the Four-Color Conjecture was eventually proven (not by Ringel or Youngs, although I think they were both involved to some extent), leaving the Klein bottle as the odd-man out.
(a) What is the "reason" for the Klein bottle's exceptionality here? (b) Does the answer to part (a) manifest in any other way – meaning, are there other theorems, patterns, etc to which the Klein bottle is an exception that can be traced back to (a)?
Best Answer
Denote by $N_c$ the non-orientable surface with $c$ pairwise disjoint crosscaps. So $N_1$ is the projective plane, $N_2$ is the Klein bottle, etc.
Then the "reason" of Klein bottle's exceptionality in Heawood conjecture is the following: for all $c \geq 3$, the complete graph $K_p$ embeds in $N_c$, where $c$ is the smallest integer which is at least $(p-3)(p-4)/6$. The case $c=2$ is exceptional, in fact $K_7$ does not embed in $N_2$. More details are here.
This result on Klein bottle was proven by Franklin, who also showed that there actually exists in $N_2$ a map with chromatic number $6$, obtained by embedding in the surface the so-called Franklin graph