**The
Chromatic Number of
the Plane & of 3-Space**

The *unit-distance graph of the plane,*
*R _{2,}* 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 *R _{2. }*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

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, R _{3}*,
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

**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