Heawood conjecture

Replacing the genus by the Euler characteristic, we obtain a formula that covers both the orientable and non-orientable cases, This relation holds, as Ringel and Youngs showed, for all surfaces except for the Klein bottle.

Philip Franklin (1930) proved that the Klein bottle requires at most 6 colors, rather than 7 as predicted by the formula.

The Franklin graph can be drawn on the Klein bottle in a way that forms six mutually-adjacent regions, showing that this bound is tight.

The upper bound, proved in Heawood's original short paper, is based on a greedy coloring algorithm.

By manipulating the Euler characteristic, one can show that every graph embedded in the given surface must have at least one vertex of degree less than the given bound.

A radially symmetric 7-colored torus – regions of the same colour wrap around along dotted lines
An 8-coloured double torus (genus-two surface) – opposite circles are linked by handles
A 6-colored Klein bottle, the only exception to the Heawood conjecture
The Franklin graph .
A partition of the torus into seven mutually adjacent regions, requiring seven colors.
Interactive Szilassi polyhedron model with each of 7 faces adjacent to every other. In the SVG image, move the mouse to rotate it. [ 1 ]