Hadwiger–Nelson problem
From Wikipedia, the free encyclopedia
In mathematics, more specifically in geometric graph theory, the Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance one from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 4,5,6 or 7.
The question can be phrased in graph theoretic terms as follows. Let G be the unit distance graph of the plane: an infinite graph with all points of the plane as vertices and with an edge between two vertices if and only if there is unit distance between the two points. Then the Hadwiger–Nelson problem is to find the chromatic number of G. As a consequence, the problem is often called "finding the chromatic number of the plane". By a result of de Bruijn and Erdős, it is equivalent to find the maximum chromatic number of any finite subgraph of the unit distance graph of the plane.
According to Jensen and Toft, the problem was first formulated by E. Nelson in 1950, and first published by Gardner in 1960. Hugo Hadwiger in 1945 had published a related result, showing that any cover of the plane by five congruent closed sets contains a unit distance in one of the sets, and he also mentioned the problem in a 1961 publication.
Contents |
[edit] Lower and upper bounds
The fact that the chromatic number of the plane must be at least four follows from the existence of a seven-vertex unit distance graph, called the Moser spindle, with chromatic number four. This graph consists of two unit equilateral triangles joined at a common vertex x. Each of these triangles is joined along another edge to another equilateral triangle; the vertices y and z of these joined triangles are at unit distance from each other. If the plane could be three-colored, the coloring within the triangles would force y and z to both have the same color as x, but then, since y and z are at unit distance from each other, we would not have a proper coloring of the unit distance graph of the plane. Therefore, at least four colors are needed to color this graph and the plane containing it.
The upper bound of seven on the chromatic number follows from the existence of a tesselation of the plane by regular hexagons, with diameter slightly less than one, that can be assigned seven colors in a repeating pattern to form a 7-coloring of the plane.
[edit] Variations of the problem
The problem can easily be extended to higher dimensions. In particular, finding the chromatic number of space usually refers to the 3-dimensional version. As with the version on the plane, the answer is not known, but has been shown to be at least 6 and at most 15.
One can also consider colorings of the plane in which the sets of points of each color are restricted to sets of some particular type (see, e.g., Croft et al.). Such restrictions may cause the required number of colors to increase, as they prevent certain colorings from being considered acceptable. For instance, if all color classes are required to be Lebesgue measurable, it is known that at least five colors are required. If all connected components of each color class are convex polygons with area bounded away from zero, then at least six colors are required (Coulson 2004).
[edit] See also
[edit] References
- de Bruijn, N.G.; Erdős, P. (1951). "A colour problem for infinite graphs and a problem in the theory of relations". Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373.
- Chilakamarri, K. B. (1993). "The unit-distance graph problem: a brief survey and some new results". Bull Inst. Combin. Appl. 8: 39–60.
- Coulson, D. (2004). "On the chromatic number of plane tilings". J. Austral. Math. Soc. 77: 191–196.
- Croft, Hallart T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. Springer-Verlag, Problem G10.
- Gardner, Martin (1960). "Mathematical Games". Scientific American 203/4: 180.
- Hadwiger, Hugo (1945). "Überdeckung des euklidischen Raumes durch kongruente Mengen". Portugal. Math. 4: 238–242.
- Hadwiger, Hugo (1961). "Ungelöste Probleme No. 40". Elem. Math. 16: 103–104.
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization, 150–152.
[edit] External links
- O'Rourke, Joseph. Problem 57: Chromatic Number of the Plane. The Open Problems Project.
- Mohar, Bojan (2001). The chromatic number of the Unit Distance Graph.
