## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  306.05121
Autor:  Bollobás, Béla; Erdös, Paul; Szemeredi, E.
Title:  On complete subgraphs of r-chromatic graphs. (In English)
Source:  Discrete Math. 13, 97-107 (1975).
Review:  Let Gr(n) be an r-chromatic graph with n vertices in each colour class. Suppose G = G3(n), and \delta (G), the minimal degree in G, is at least n+t(t \geq 1). We prove that G contains at least t3 triangles but does not have to contain more than 4t3 of them. Furthermore, we give lower bounds for s such that G contains a complete 3-partite grpah with s vertices in each class. Let

fr(n) = max {\delta (G): G = Gr(n),   G does not contain a complete graph with r vertices} .

We obtain various results on fr(n). In particular, we prove that if cr = limn ––> oo fr(n)/n, then limr ––> oo (cr-(r-2)) \geq ½ and we conjecture that equality holds. We prove several other results and state a number of unsolved problems.
Classif.:  * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag