18
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ In my mind I classify this as another "low-dimensional obstruction"; in most theorems of this kind (e.g. A_n is simple, the classification of finite simple groups) one should expect finitely many counterexamples because there may not be enough room for generic behavior to happen initially. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 12, 2011 at 14:41

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ The complete graph $K_6$ easily embeds in the real projective plane $N_1$ (as antipodal quotient of an icosahedron), hence in $N_2$ (and a Möbius band, by the way). $\endgroup$
    – BS.
    Commented Jan 12, 2011 at 11:36
8
$\begingroup$

Even though there is always a preference towards uniformity in understanding of general results such as Heawood's theorem, this somehow feels like the wrong question to ask. While I am not familiar all the way with all the proofs involved (the full proof is massive, and involves the four color theorem as well) it is obvious that there are many special cases treated separately, with the most difficult cases being the planar case and $g\in \{59, 83,158,257\}$. So even if the resulting formula is uniform, the behavior of each case is not obviously so.

In the end, the answer to your question boils down to the reason that Francesco Polizzi mentions in his answer, and can perhaps be elaborated a bit more by mentioning the improvement of the Heawood result by Dirac, Albertson and Hutchinson that every graph in $\Sigma$ is actually $H(\Sigma)-1$ colorable unless it has a subgraph isomorphic to a complete graph on $H(\Sigma)$ vertices. You can see here that the Klein bottle is expected to behave differently as $K_7$ doesn't embed in it, but suddenly we get the planar case as another exception and the projective plane was dealt separately too.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your second paragraph is very interesting - thanks for the info ;) $\endgroup$
    – Dr Shello
    Commented Jan 13, 2011 at 5:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .