On the Connectivity of Unit Distance Graphs

On the Connectivity of Unit Distance Graphs, by Michael Reid
Graphs and Combinatorics 12 (1996), no. 3, pp. 295-303.
[DOI] [Math Reviews] [Zentralblatt]
.dvi (40k) .ps (503k) .ps.gz (256k) .pdf (120k)
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 G0(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 : G0(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 K4 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 Kd is connected for all K when d ≥ 5 .
[1] Klaus G. Fischer, Additive K-colorable Extensions of the Rational Plane, Discrete Mathematics 82 (1990), no. 2, pp. 181-195. [Math Reviews] [Zentralblatt]
Research page Home page E-mail
Updated January 8, 2008.