PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
Heawood number (Theorem)

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

$\displaystyle H(S)=\left\lfloor\frac{7+\sqrt{49-24 e(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:

$\displaystyle \begin{xy}{*!C\xybox{\xymatrix@R=0pt{ 1\ar@{-}[r]\ar@{-}[dd]\ar@{... ... & & 5\ar@{-}[dd] \\ \\ 1\ar@{-}[r] & 2\ar@{-}[r] & 3\ar@{-}[r] & 1}}} \end{xy}$    

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.



"Heawood number" is owned by bbukh.
(view preamble)

View style:

See Also: four-color conjecture
Log in to rate this entry.
(view current ratings)

Cross-references: torus, bound, vertices, complete graph, Klein bottle, chromatic number, number, four-color conjecture, Euler characteristic, sphere, graph, colors, maximal number, upper bound, surface
There is 1 reference to this entry.

This is version 9 of Heawood number, born on 2003-01-05, modified 2006-06-11.
Object id is 3876, canonical name is HeawoodNumber.
Accessed 3002 times total.

Classification:
AMS MSC: 05C10 (Combinatorics :: Graph theory :: Topological graph theory, imbedding)
 05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)