##
**Zentralblatt MATH**

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

**Zbl.No: ** 458.05045

**Autor: ** Burr, Stefan A.; Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.

**Title: ** An extremal problem in generalized Ramsey theory. (In English)

**Source: ** Ars Comb. 10, 193-203 (1980).

**Review: ** Chvátal proved that the Ramsey number R(K_{m},T) of a complete graph on m vertices and a tree on n vertices is given by (m-1) (n-1)+1. In this article, the authors consider connected graphs on n vertices and q edges satisfying the equation R(K_{m},G) = (m-n)(n-1)+1. Such graphs are called m-good. They then define f(m,n) as the largest q for which every connected graph on n vertices and q edges is m-good. Similarly, g(m,n) is the largest q for which there exist a connected m-good graph on n vertices with q edges. The authors then establish the following bounds: 1. For all n \geq 4, f(3,n) \geq (17n+1)/15, 2. For every \epsilon > 0, if n is sufficiently large, then f(3,n) < (27/4+\epsilon)n(log n)^{2}, 3. There exist positive constants A, B so that: An^{3/2}(log n)^{ ½} < g(3,n) < Bn^{5/3}(log n)^{2/3} for all n sufficiently large. the authors also pressent vounds for f(m,n) and g(m,n) for arbitrary m and pose the question of determining whether f(n)/n ––> oo as n ––> oo.

**Reviewer: ** W.Trotter

**Classif.: ** * 05C55 Generalized Ramsey theory

**Keywords: ** Ramsey number

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag