Graphs and Combinatorics
(1996), no. 3, pp. 295-303.

On the Connectivity of Unit Distance Graphs,
by Michael Reid

Graphs and Combinatorics
(1996), no. 3, pp. 295-303.

Abstract

A well-known open problem asks for the fewest number of colors necessary
to color the points of the plane so that any two points at distance 1
have different colors.
If one considers only points with rational coordinates,
then 2 colors suffice.
Several authors have considered
the problem of coloring all points whose coordinates lie in some real
quadratic field, or more generally, a subfield of the real numbers.
Fischer [1] describes "additive colorings" as follows.
Firstly, let *G*_{0}(*K*)
be the connected component of the underlying graph,
whose vertices are points in *K*² ,
with an edge between two points at distance 1 .
Then an additive coloring is a homomorphism
*f* : *G*_{0}(*K*) ---> *A* ,
where *A* is a finite abelian group.
As a result, the connectedness of the underlying graph becomes relevant.
In this paper, we show that if *K* is a number field,
then the graph on *K*² is connected
if and only if -1 is not a square in *K* .
We also consider higher dimensions, and show that the graph on
*K*³ is connected if and only if the graph on
*K*^{4} is connected, and give necessary and
sufficient conditions for this, in terms of the splitting of the
rational prime 2 in *K* .
Lastly, we show that the graph on *K*^{d}
is connected for all *K* when *d* ≥ 5 .

Reference

[1]
Klaus G. Fischer,
Additive *K*-colorable Extensions of the Rational Plane,
Discrete Mathematics
(1990), no. 2, pp. 181-195.
[Math Reviews]
[Zentralblatt]

Updated January 8, 2008.