## You are here

HomeHeawood number

## Primary tabs

# Heawood number

The Heawood number of a surface is an upper bound for the maximal number of colors needed to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces except the sphere that no more than

$H(S)=\left\lfloor\frac{7+\sqrt{49-24e(S)}}{2}\right\rfloor$ |

colors are needed to color any graph embedded in a surface of Euler characteristic $e(S)$. The case of the sphere is the four-color conjecture which was settled by Appel and Haken in 1976. The number $H(S)$ became known as Heawood number in 1976. Franklin proved that the chromatic number of a graph embedded in the Klein bottle can be as large as $6$, but never exceeds $6$. Later it was proved in the works of Ringel and Youngs that the complete graph of $H(S)$ vertices can be embedded in the surface $S$ unless $S$ is the Klein bottle. This established that Heawood’s bound could not be improved.

For example, the complete graph on $7$ vertices can be embedded in the torus as follows:

$\xy{*!C\xybox{\xymatrix@R=0pt{1\ar@{-}[r]\ar@{-}[dd]\ar@{-}[dddr]&2\ar@{-}[r]% \ar@{-}[ddd]\ar@{-}[dddr]\ar@{-}[ddrr]&3\ar@{-}[r]\ar@{-}[ddr]&1\ar@{-}[dd]\\ \\ 4\ar@{-}[dd]\ar@{-}[dr]&&&4\ar@{-}[dd]\\ &6\ar@{-}[r]\ar@{-}[dddr]&7\ar@{-}[ddd]\ar@{-}[dddr]\ar@{-}[dr]\ar@{-}[ur]&\\ 5\ar@{-}[dd]\ar@{-}[ur]\ar@{-}[ddr]\ar@{-}[ddrr]&&&5\ar@{-}[dd]\\ \\ 1\ar@{-}[r]&2\ar@{-}[r]&3\ar@{-}[r]&1}}}$ |

# References

- 1 Béla Bollobás. Graph Theory: An Introductory Course, volume 63 of GTM. Springer-Verlag, 1979. Zbl 0411.05032.
- 2 Thomas L. Saaty and Paul C. Kainen. The Four-Color Problem: Assaults and Conquest. Dover, 1986. Zbl 0463.05041.

## Mathematics Subject Classification

05C15*no label found*05C10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier