Distances forbidden by some two-coloring of \(\mathbb{Q}^ 2\) (Q1813730): Difference between revisions

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. \textit{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. \textit{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}\).