##
**Zentralblatt MATH**

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

**Zbl.No: ** 659.05079

**Autor: ** Erdös, Paul; Godsil, C.D.; Krantz, S.G.; Parsons, T.D.

**Title: ** Intersection graphs for families of balls in R^{n}. (In English)

**Source: ** Eur. J. Comb. 9, No.5, 501-506 (1988).

**Review: ** Let B(x,r) denote a ball, (either open or closed) of radius r > 0 and center x, in the Euclidean space **R**^{n}. Let \mu[A] be the n-dimensional Lebesgue volume of the subset A of **R**^{n} and let \epsilon denote a real number in (0,1]. A pair of balls B, B' are said to be \epsilon-disjoint if \mu(B\cap B') \leq (1-\epsilon)**max** **{**\mu(B),\mu(B')**}**. A family F of balls is \epsilon-disjoint, if the balls are pairwise \epsilon-disjoint. Denote by \Gamma_{n,\epsilon} the set of all intersection graphs \Gamma(F) for \epsilon-disjoint families F of balls in **R**^{n}. The authors show that there exists a least integer d = d(n,\epsilon) such that every graph in \Gamma_{n,\epsilon} has a vertex of degree at most d and also show that there exists a least integer m = m(n) such that every intersection graph \Gamma(F), where F is a family of balls, has a vertex v such that the subgraph induced by the vertices adjacent to v contains no independent set of size greater than m.

**Reviewer: ** R.C.Entringer

**Classif.: ** * 05C99 Graph theory

**Keywords: ** epsilon-disjoint; ball; Euclidean space; intersection graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag