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.
suggests the following warm-up problems, whose answers are known: 1) What
complete bipartite graphs are subgraphs of
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].
[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
[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 firstname.lastname@example.org)
Send comments to email@example.com