## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  694.05031
Autor:  Erdös, Paul; Lovász, László; Vesztergombi, K.
Title:  On the graph of large distances. (In English)
Source:  Discrete Comput. Geom. 4, No.6, 541-549 (1989).
Review:  Let S be a set of n points in the plane and let d1 > d2 > ... 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 18k2 there is \chi(G)S,k)) \leq 7 and for n > 25000k2 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.