Computational geometry column 46

ABSTRACT

The old problem of determining the chromatic number of the plane is revisited.

The question of the chromatic number of the Euclidean plane E² has been unresolved for over fifty years. Informally, the question asks: How many colors are needed to paint the plane so that no two points a unit distance apart are painted the same color? If the same question is asked of the line, the answer is 2: Coloring [0,1) red, [1,2) blue, etc., ensures that no two unit-separated points have the same color. Here I report on a few new developments, and some related open problems that are perhaps easier.

One can view the question as asking for the chromatic number X(E²) of the infinite <i>unit-distance graph G</i>, with every point in the plane a node, and an are between two nodes if they are separated by a unit distance. Erdös and de Bruijn showed [EdB51] that the chromatic number of the plane is attained for some finite subgraph of <i>G.</i> This result led to narrowing the answer to 4 ≤ X(E²) ≤7. For example, the lower bound of 4 is established by the "Moser graph" shown in Fig. 1, which needs 4 colors.

REFERENCES

• 1: {EdB51} P. Erdös and N. G. de Bruijn. A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math., 13:371--373, 1951.
• 2: {Gra03} R. L. Graham. Euclidean Ramsey theory, August 2003. Lecture at Mathematical Sciences Research Institute, Berkeley. http://www.msri.org/publications/video/index07.html.
• 3: R. L. Graham, Euclidean Ramsey theory, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 4: {Gra04b} R. L. Graham. Open problems in Euclidean Ramsey theory. Geocombinatorics, XIII(4):165--177, April 2004.
• 5: {Sha76} L. Shader. All right triangles are Ramsey in E2. J. Combinatorial Theory Series A, 20:385--389, 1976.
• 6: Saharon Shelah , Alexander Soifer, Axiom of choice and chromatic number of the plane, Journal of Combinatorial Theory Series A, v.103 n.2, p.387-391, August 2003 [doi>10.1016/S0097-3165(03)00102-X]