-
四色猜想的提出来自英国。1852年，毕业于伦敦大学的格思里(Guthrie)来到一家科研单位搞地图染色工作时，一个现象吸引住了他，就是每幅地图都可以用四种颜色染色，使得享有共同国界线国家的版图染不相同的颜色，即使国界线两侧异色。这个结论看似简单，但从数学上加以严格证明却难倒了许多数学家。1872年，英国数学家凯利(Cayley)正式向伦敦数学学会提出了这个问题，从此“四色猜想”在数学界备受瞩目。19716
- 上一篇：驾驶培训系统国内外研究现状
- 下一篇：网络游戏国内外研究现状和发展趋势
1878一1880年两年间，肯普(Kempe)和泰勒(Tait)两人分别发表了证明四色猜想的论文，宣布证明了四色定理，人们都认为“四色猜想”的奥秘就此已经被揭开了。但短短十余年之后，也就是1890年，数学家赫伍德(Heawood)以自己的精确计算指出Kempe的证明是错误的，但却利用他巧妙的证明技巧证明五色定理成立。1891年，彼得森(Petersen)指出了Tait证明中的错误，并利用Tait的方法证明四色猜想与如下命题等价：任何一个2边连通3正则平面图的边色数为3。
进入20世纪后，数学狂人们对四色猜想的证明基本上是都是按照Kempe的证明技巧在进行。1913年，伯克霍夫在肯普的基础上引进了一些新技巧，美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色染色。1950年，有人从22国推进到35国。直到1976年，美国数学家阿佩尔(K.Appel)和黑肯(W.Hakan)首次应用计算机证明了这一难题，从此“四色猜想”成为了“四色定理”。他们从1976年1月至6月在三部计算机上用了1200小时，作了近百亿次逻辑判断才得出结果，证明的正确性如果不借助计算机也无法检验。在1996年，N.Robertson等又给出了一个简化的计算机证明。尽管迄今为止仍没有得到非计算机的理论性证明，但图染色理论的意义远不止如此。
对一般情况，求点染色问题就是给出了 的范围(用 的参数表示)，然后对某些特殊图类，确定出了 的确切值。