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