×

Distances forbidden by some two-coloring of \(\mathbb{Q}^ 2\). (English) Zbl 0771.05039

A very famous problem by P. Erdős and R. Nelson asks if the points \(R^ 2\) in the plane can be 4-coloured such that no two points of distance 1 are coloured the same. D. R. Woodall [J. Comb. Theory, Ser. A 14, 187-200 (1973; Zbl 0251.50003)] proved that all the points \(\mathbb{Q}^ 2\) in the plane with rational coordinates can be 2-coloured such that no two points of distance 1 are coloured the same. P. D. Johnson [Discrete Math. 79, No. 2, 191-195 (1990; Zbl 0701.05005)] extended Woodall’s result to 2-colourings of \(\mathbb{Q}^ 2\) where no two points have a distance in certain sets \(D\). The main results of the present interesting paper is to show that in a sense Johnson’s result is optimal: \(\mathbb{Q}^ 2\) can be 2-coloured with no two points of a distance in \(D\) coloured the same if and only if \(D\) does not contain two distances \(d_ 1\) and \(d_ 2\) such that (i) \(d_ 1\) and \(d_ 2\) are both distances between points in \(\mathbb{Q}^ 2\), and (ii) there are positive integers \(p\) and \(q\) with \(p+q\) odd such that \(d_ 1/d_ 2=\sqrt{p/q}\).
Reviewer: B.Toft (Odense)

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Johnson, P. D., Coloring abelian groups, Discrete Math., 40, 219-223 (1982) · Zbl 0485.05009
[2] Johnson, P. D., Two-colorings of a dense subgroup of \(Q^n\) that forbid many distances, Discrete Math., 79, 2, 191-195 (1989/90) · Zbl 0701.05005
[3] Woodall, D. R., Distances realized by sets covering the plane, J. Combinat. Th., 14, 187-200 (1973), (A) · Zbl 0251.50003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.