Discrete Mathematics
(1990), no. 1, pp. 53-56.

Discrete Mathematics
(1990), no. 1, pp. 53-56.

Abstract

Woodall [2] has shown that the rational points in the plane may be
colored with two colors so that any two points at distance 1 have
different colors.
Johnson [1] extended this to show that there is a two-coloring that
"forbids" not only the distance 1 , but also every distance of the form
√(*p*/*q*) , where *p* and
*q* are odd positive integers.
Johnson's coloring also forbids some other distances, such as
√6 , because no two rational points are precisely
that far apart.
We show that Johnson's coloring is optimal, in the sense that, if
*d* actually occurs as a distance, and *d* is not of the form
√(*p*/*q*) , for odd positive integers
*p* and *q* , then no two-coloring of
**Q**² forbids both the distance 1 and *d* .
This settles one of Johnson's questions.
We also consider two-colorings of **Q**³ ,
and solve two more of his problems.

References

[1]
Peter D. Johnson, Jr.,
Two-colorings of a dense subgroup of **Q**^{n},
Discrete Mathematics
(1990), no. 2, pp. 191-195.
[Math Reviews]
[Zentralblatt]

[2]
D. R. Woodall,
Distances realized by sets covering the plane,
Journal of Combinatorial Theory, Series A
(1973) pp. 187-200.
[Math Reviews]
[Zentralblatt]

Updated January 8, 2008.