##
**Zentralblatt MATH**

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

**Zbl.No: ** 277.05135

**Autor: ** Bollobás, Béla; Erdös, Paul

**Title: ** On the structure of edge graphs. (In English)

**Source: ** Bull. Lond. Math. Soc. 5, 317-321 (1973).

**Review: ** Let K_{r}(t) be a graph with r groups of t vertices, each two vertices of which are connected iff they belong to different groups. denote g(n,r, \epsilon) the minimal such t that any graph with n vertices and m = [((r-2)/2(r-1)+\epsilon)n^{2}] edges contains a K_{r}(t), (\epsilon > 0). In this article it is proved that for any r and 0 < \epsilon < {1 over 2}(r-1) there exist constants c_{1},c_{2} such that c_{1} log n \leq g(n,r, \epsilon) \leq c_{2} log n for sufficiently large n and c_{2} ––> 0 if \epsilon ––> 0.

**Reviewer: ** St.Znám

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C99 Graph theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag