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(Km,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(Km,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: An3/2(log n) ½ < g(3,n) < Bn5/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