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 Rd. Let d1 > d2 > ... > dk > ... 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 dk. 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 Rd such that no d of its elements are contained in a (d-2)-dimensional subspace, and n > 2(d+1)dkd, 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 Rd 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