|
|
| Line 1: |
Line 1: |
| In [[mathematics]], the '''Heawood number''' of a [[surface]] is a certain [[upper bound]] for the maximal number of colors needed to color any [[graph (mathematics)|graph]] [[embedding|embedded]] in the surface.
| | span.mwe-math-mathml-inline, div.mwe-math-mathml-display { |
| | | display: none !important; |
| In 1890 Heawood proved for all surfaces ''except'' the [[sphere]] that no more than
| | } |
| | | span.mwe-math-mathml-inline + .mwe-math-fallback-image-inline { |
| :<math> H(S)=\left\lfloor\frac{7+\sqrt{49-24 e(S)}}{2}\right\rfloor</math>
| | display: inline !important; |
| colors are needed to color any graph embedded in a surface of [[Euler characteristic]] <math>e(S)</math>. The case of the sphere is the [[four-color conjecture]] which was settled by [[Kenneth Appel]] and [[Wolfgang Haken]] in 1976. The number <math>H(S)</math> became known as Heawood number in 1976.
| | } |
| | | div.mwe-math-mathml-display + .mwe-math-fallback-image-display { |
| Franklin proved that the [[chromatic number]] of a graph embedded in the [[Klein bottle]] can be as large as <math>6</math>, but never exceeds <math>6</math>. Later it was proved in the works of [[Gerhard Ringel]] and J. W. T. Youngs that the [[complete graph]] of <math>H(S)</math> vertices can be embedded in the surface <math>S</math> unless <math>S</math> is the [[Klein bottle]]. This established that Heawood's bound could not be improved.
| | display: block !important; |
| | | } |
| For example, the complete graph on <math>7</math> vertices can be embedded in the [[torus]] as follows:
| |
| | |
| [[Image:Heawood number.png]]
| |
| | |
| ==References==
| |
| * [[Béla Bollobás|Bollobás, Béla]], ''Graph Theory: An Introductory Course'', volume 63 of GTM, Springer-Verlag, 1979. [http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0463.05041 Zbl 0411.05032].
| |
| * [[Thomas L. Saaty|Saaty, Thomas L.]] and [[Paul Chester Kainen|Kainen, Paul C.]]; ''The Four-Color Problem: Assaults and Conquest'', Dover, 1986. [http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0411.05032 Zbl 0463.05041].
| |
| | |
| {{PlanetMath attribution|id=3876|title=Heawood number}} | |
| | |
| [[Category:Topological graph theory]]
| |
| [[Category:Graph coloring]]
| |
span.mwe-math-mathml-inline, div.mwe-math-mathml-display {
display: none !important;
}
span.mwe-math-mathml-inline + .mwe-math-fallback-image-inline {
display: inline !important;
}
div.mwe-math-mathml-display + .mwe-math-fallback-image-display {
display: block !important;
}