请输入您要查询的字词:

 

单词 HeawoodNumber
释义

Heawood number


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

H(S)=7+49-24e(S)2

colors are needed to color any graph embedded in a surface ofEuler characteristicMathworldPlanetmath 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) becameknown as Heawood number in 1976. Franklin proved that the chromatic numberMathworldPlanetmathof a graph embedded in the Klein bottleMathworldPlanetmath can be as large as 6,but never exceeds 6. Later it was proved in the works of Ringeland Youngs that the complete graphMathworldPlanetmath of H(S) vertices can beembedded in the surface S unless S is the Klein bottle. Thisestablished 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=0pt1\\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 TheoryMathworldPlanetmath: An Introductory Course, volume 63 of GTM. Springer-Verlag, 1979. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0411.05032Zbl 0411.05032.
  • 2 Thomas L. Saaty and Paul C. Kainen. The Four-Color Problem: Assaults and Conquest. Dover, 1986. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0463.05041Zbl 0463.05041.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 6:45:25