Four-Color Problem

four-color problem

[¦fȯr ′kəl·ər ‚präb·ləm]
The problem of proving the statement that, given any map in the plane, it is possible to color the regions with four colors so that any two regions with a common boundary have different colors.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
The following article is from The Great Soviet Encyclopedia (1979). It might be outdated or ideologically biased.

Four-Color Problem


the problem of whether four different colors are sufficient to color any map so that no two regions having a common boundary segment have the same color. Although the conjecture that four colors are enough was proved for all known special cases, the problem long remained unsolved. Not until 1976 was a report of a rigorous mathematical proof published.

First formulated as a mathematical problem in the mid-19th century, the four-color problem became widely known through the lectures of the British mathematician A. de Morgan. A rigorous formulation of the problem requires that the regions in question be bounded by Jordan curves—that is, by simple closed curves. It can be easily proved that five colors are always sufficient to color such a map.

In the corresponding problem for space, no number of colors is sufficient.


Appel, K., and W. Haken. Bulletin of the American Mathematical Society, vol. 82, no. 5, pp. 711–12.
The Great Soviet Encyclopedia, 3rd Edition (1970-1979). © 2010 The Gale Group, Inc. All rights reserved.
References in periodicals archive ?
For example, Sinclair had her students investigate the historical four-color problem. The question posed by the four-color problem is "whether every map on the plane or sphere can be colored with no more than four colors in such a way that neighboring regions are never colored alike" (Tymoczko, 1979, p.
The four-color problem poses this hypothesis: Every map can be colored with at most four colors in such a way that all neighboring countries are colored differently.
The immediate reality of programming is dominated by the nature of the application at hand, which may be concerned, for example, with business and accounting practices, or graphics, or linguistics, or the simulation of physical phenomena, or even mathematics itself (as in testing solutions to the four-color problem).