## 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 Kr(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)n2] edges contains a Kr(t), (\epsilon > 0). In this article it is proved that for any r and 0 < \epsilon < {1 over 2}(r-1) there exist constants c1,c2 such that c1 log n \leq g(n,r, \epsilon) \leq c2 log n for sufficiently large n and c2 ––> 0 if \epsilon ––> 0.
Reviewer:  St.Znám
Classif.:  * 05C35 Extremal problems (graph theory)
05C99 Graph theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag