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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page