On the graph of large distances (Q908937)

Let \(S\) be a set of \(n\) points in the plane and let \(d_1>d_2>..\). be the different distances determined by the set \(S\). The graph \(G(S,k)\) is considered whose vertex set is S and in which two vertices are adjacent if and only if their distance is at least \(k\). The chromatic number \(\chi(G(S,k))\) of \(G(S,k)\) is studied. It is proved that for \(n\geq 18k^2\) there is \(\chi(G)S,k))\leq 7\) and for \(n>25000k^2\) there is \(\chi(G(S,k))\leq 3\). Further the particular case is treated, when \(S\) is the set of vertices of a convex polygon. Then \(\chi(G(S,k))\leq 3k\) and the graph \(G(S,k)\) has a vertex of degree at most \(3k-1\).