##
**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 G_{r}(n) be an r-chromatic graph with n vertices in each colour class. Suppose G = G_{3}(n), and \delta (G), the minimal degree in G, is at least n+t(t \geq 1). We prove that G contains at least t^{3} triangles but does not have to contain more than 4t^{3} 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 f_{r}(n) = **max** **{**\delta (G): G = G_{r}(n), G does not contain a complete graph with r vertices**}** . We obtain various results on f_{r}(n). In particular, we prove that if c_{r} = **lim**_{n ––> oo} f_{r}(n)/n, then **lim**_{r ––> oo} (c_{r}-(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