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 Kp-independence numbers. (In English)
Source: Comb. Probab. Comput. 3, No.3, 297-325 (1994).
Review: The Kp-independence number \alphap(G) of a graph G is the maximum order of an induced subgraph of G that contains no Kp. In this paper, the authors study the following problem: For integers r, p, m > 0 and graphs L1,..., Lr, what is the maximum number of edges in a graph G of order n such that \alphap(G) \leq m and there is an edge-colouring of G with r colours such that the jth colour class contains no copy of Lj, for j = 1,..., r (this maximum number is denoted by RTp(n, L1,..., Lr, m))? They obtain several results for graphs G of order n with small Kp-independence number \alphap(G). Some structure theorems are given for the case \alphap(Gn) = o(n), showing that there are graphs with fairly simple structure that are within o(n2) 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 \thetap(Kq) = limn ––> oo {RTp(n, Kq, 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; Kp-independence number; edge-colouring; structure theorems; extremal size
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag