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