请输入您要查询的字词:

 

单词 Four-Color Theorem
释义

Four-Color Theorem

The four-color theorem states that any map in a Plane can be colored using four-colors in such a way that regionssharing a common boundary (other than a single point) do not share the same color. This problem is sometimes also calledGuthrie's Problem after F. Guthrie, who first conjectured the theorem in 1853. The Conjecture was thencommunicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on theconjecture.


Fallacious proofs were given independently by Kempe (1879) and Tait (1880). Kempe's proof was accepted for adecade until Heawood showed an error using a map with 18 faces (although a map with nine faces suffices to show thefallacy). The Heawood Conjecture provided a very general result for map coloring, showing that in aGenus 0 Space (i.e., either the Sphere or Plane), six colors suffice. Thisnumber can easily be reduced to five, but reducing the number of colors all the way to four proved very difficult.


Finally, Appel and Haken (1977) announced a computer-assisted proof that four colors were Sufficient. However, becausepart of the proof consisted of an exhaustive analysis of many discrete cases by a computer, some mathematicians do notaccept it. However, no flaws have yet been found, so the proof appears valid. A potentially independent proof has recentlybeen constructed by N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas.


Martin Gardner (1975) played an April Fool's joke by (incorrectly) claiming that the map of 110 regions illustrated belowrequires five colors and constitutes a counterexample to the four-color theorem.

See also Chromatic Number, Heawood Conjecture, Map Coloring, Six-Color Theorem


References

Four-Color Problem

Appel, K. and Haken, W. ``Every Planar Map is Four-Colorable, I and II.'' Illinois J. Math. 21, 429-567, 1977. Appel, K. and Haken, W. ``The Solution of the Four-Color Map Problem.'' Sci. Amer. 237, 108-121, 1977.

Appel, K. and Haken, W. Every Planar Map is Four-Colorable. Providence, RI: Amer. Math. Soc., 1989.

Barnette, D. Map Coloring, Polyhedra, and the Four-Color Problem. Providence, RI: Math. Assoc. Amer., 1983.

Birkhoff, G. D. ``The Reducibility of Maps.'' Amer. Math. J. 35, 114-128, 1913.

Chartrand, G. ``The Four Color Problem.'' §9.3 in Introductory Graph Theory. New York: Dover, pp. 209-215, 1985.

Coxeter, H. S. M. ``The Four-Color Map Problem, 1840-1890.'' Math. Teach., Apr. 1959.

Franklin, P. The Four-Color Problem. New York: Scripta Mathematica, Yeshiva College, 1941.

Gardner, M. ``Mathematical Games: The Celebrated Four-Color Map Problem of Topology.'' Sci. Amer. 203, 218-222, Sep. 1960.

Gardner, M. ``The Four-Color Map Theorem.'' Ch. 10 in Martin Gardner's New Mathematical Diversions from Scientific American. New York: Simon and Schuster, pp. 113-123, 1966.

Gardner, M. ``Mathematical Games: Six Sensational Discoveries that Somehow or Another have Escaped Public Attention.'' Sci. Amer. 232, 127-131, Apr. 1975.

Gardner, M. ``Mathematical Games: On Tessellating the Plane with Convex Polygons.'' Sci. Amer. 232, 112-117, Jul. 1975.

Kempe, A. B. ``On the Geographical Problem of Four-Colors.'' Amer. J. Math. 2, 193-200, 1879.

Kraitchik, M. §8.4.2 in Mathematical Recreations. New York: W. W. Norton, p. 211, 1942.

Ore, Ø. The Four-Color Problem. New York: Academic Press, 1967.

Pappas, T. ``The Four-Color Map Problem: Topology Turns the Tables on Map Coloring.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 152-153, 1989.

Robertson, N.; Sanders, D. P.; and Thomas, R. ``The Four-Color Theorem.'' http://www.math.gatech.edu/~thomas/FC/fourcolor.html.

Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, 1986.

Tait, P. G. ``Note on a Theorem in Geometry of Position.'' Trans. Roy. Soc. Edinburgh 29, 657-660, 1880.


随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/4/8 10:57:35