##
**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 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.

**Reviewer: ** B.Zelinka

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C38 Paths and cycles

52A10 Convex sets in 2 dimensions (including convex curves)

**Keywords: ** point of the plane; distance in the plane; chromatic number

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag