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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page