##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 683.05020

**Autor: ** Erdös, Paul; Lovász, László; Vesztergombi, K.

**Title: ** The chromatic number of the graph of large distances. (In English)

**Source: ** Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 547-551 (1988).

**Review: ** [For the entire collection see Zbl 673.00009.]

Let S be a set of n points in **R**^{d}. Let d_{1} > d_{2} > ... > d_{k} > ... be the distances between the points in S. We assign the following graph G(S, \leq k) tothe set S: the vertices of G(S, \leq k) correspond to the points in S, two vertices being connected iff the distance of the corresponding points is at least d_{k}. In a previous paper [Discrete Comput. Geom. 4, No.6, 541-549 (1989; Zbl 694.05031)], the authors studied the chromatic number \chi(G(S, \leq k)) of this graph in the plane. In this paper the problem is studied in higher dimensions and it is proved that if S is a set of n points in **R**^{d} such that no d of its elements are contained in a (d-2)-dimensional subspace, and n > 2(d+1)^{d}k^{d}, then \chi(G(S, \leq k)) \leq g(d)+d-1, where g(d) denotes the least number of parts into which the d-dimensional unit ball can be cut so that the diameter of each part is at most 1. Moreover, for every d \geq 2 there exists a k and there exist arbitrarily large (even infinite) sets of points in **R**^{d} such that no d of their elements are contained in a (d-2)-dimensional subspace and \chi(G(S, \leq k) = g(d)+d-1.

**Reviewer: ** I.Tomescu

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

**Keywords: ** Borsuk conjecture; d-dimensional space; Carathéodory's theorem; unit ball; d-dimensional complex; chromatic number

**Citations: ** Zbl 673.00009

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag