The Chromatic Number of the Plane & of 3-Space

The unit-distance graph of the plane, R2, has as its vertex set the points of the Euclidean plane, with two vertices joined by an edge if and only if the corresponding points are of distance 1. Finding the chromatic number of this graph is sometimes phrased as:

Problem: Find the chromatic number of the plane.

It is not too hard to show that the plane can be 7-colored. The desired coloring is based on the infinite hexagonal grid. A unit-distance (plane) graph is any subgraph of  R2. It is not too difficult to show that there is a (finite) 4-chromatic unit-distance graph. It follows that the chromatic number of the plane  is either 4,5,6 or 7.

Robert Hochberg suggests the following warm-up problems, whose answers are known: 1) What complete bipartite graphs are subgraphs of the plane unit-distance graphs? 2) What is the smallest 4-chromatic subgraph of the unit-distance graph? 3) Show that the Petersen graph is a subgraph of the unit-distance graph.

Robert Hochberg also suggests finding the smallest 4-chromatic subgraph unit-distance graph with a given girth. Hochberg and O'Donnell have found an example of order 23 with girth 4, and an example of order 45 with girth 5. O'Donnell has found an example of girth 12 with a very large number of vertices.

The problem is sometimes called the Hadwiger-Nelson problem. It first appeared in [G],  A survey appears in [C].

The problem naturally generalizes to 3-dimensional space. Naturally, the 3-dimensional unit-distance graph, R3, has as its vertex set the points of Euclidean 3-space, with two vertices joined by an edge if and only if the corresponding vertices are of distance 3. Finding the chromatic number of R3  is sometimes phrased as:

Problem: Find the chromatic number of space.

Nechushtan [N]  shows that the chromatic number of space is at least 6, improving the best previously known lower bound of 5. The best know upper bound is 21 [BT].

References:

[BT] M. Bona and G. Toth, A Ramsey-type problem on right-angled triangles in 3-space, Discrete Math 150 (1-3) (1996) 61-67.

[C] K.B. Chilakamarri, The unit-distance graph problem: a brief survey and some new results, Bull Inst. Combin. Appl. 8 (1993) 39-60.

[G]  M. Gardner, Mathematical Games, Scientific Amer,. 203, No. 4. October (1960) 180.

[N] O. Nechushtan, On the space chromatic number, Discrete Mathematics 256 (2002) 499-507.

Submitted by: Dan Archdeacon (with thanks to hochberg@dimacs.rutgers.edu)

Send comments to dan.archdeacon@uvm.edu

November, 2003