##
**Zentralblatt MATH**

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

**Zbl.No: ** 812.05031

**Autor: ** Erdös, Paul; Hajnal, András; Simonovits, M.; Sós, V.T.; Szemerédi, E.

**Title: ** Turán-Ramsey theorems and K_{p}-independence numbers. (In English)

**Source: ** Comb. Probab. Comput. 3, No.3, 297-325 (1994).

**Review: ** The K_{p}-independence number \alpha_{p}(G) of a graph G is the maximum order of an induced subgraph of G that contains no K_{p}. In this paper, the authors study the following problem: For integers r, p, m > 0 and graphs L_{1},..., L_{r}, what is the maximum number of edges in a graph G of order n such that \alpha_{p}(G) \leq m and there is an edge-colouring of G with r colours such that the jth colour class contains no copy of L_{j}, for j = 1,..., r (this maximum number is denoted by RT_{p}(n, L_{1},..., L_{r}, m))? They obtain several results for graphs G of order n with small K_{p}-independence number \alpha_{p}(G). Some structure theorems are given for the case \alpha_{p}(G_{n}) = o(n), showing that there are graphs with fairly simple structure that are within o(n^{2}) of the extremal size; the structure is described in terms of the edge densities between certain sets of vertices. They also study the problem of determining the asymptotic value of \theta_{p}(K_{q}) = **lim**_{n ––> oo} {RT_{p}(n, K_{q}, o(n))\over\binom{n}{2}} for p < q. They list several open problems and make some conjectures in the paper.

**Reviewer: ** Z.Chen (Indianapolis)

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

05C55 Generalized Ramsey theory

05C15 Chromatic theory of graphs and maps

05C50 Graphs and matrices

**Keywords: ** Turán-Ramsey theorems; chromatic number; K_{p}-independence number; edge-colouring; structure theorems; extremal size

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag