Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  526.05031
Autor:  Erdös, Paul; Hajnal, András; Sos, Vera T.; Szemeredi, E.
Title:  More results on Ramsey-Turán type problems. (In English)
Source:  Combinatorica 3, 69-81 (1983).
Review:  In [Combinat. Struct. Appl., Proc. Calgary Internat. Conf. Calgary 1969, 407-410 (1970; Zbl 253.05145)] V.T.Sós raised a general scheme of new problems that can be considered as common generalizations of the problems treated in the classical results of Ramsey and Turán. This paper is a continuation of a sequence of papers on this subject.
One of the main results is the following: Given k \geq 2 and \epsilon > 0, let Gn be a sequence of graphs of order n size at least (½)(\frac{3k-5}{3k-2}+\epsilon)n2 edges such that the cardinality of the largest independent set in Gn is o(n). Let H be any graph of arboricity at most k. Then there exists an n0 such that all Gn with n > n0 contain a copy of H. This result is best possible in the case H = K2k.
Reviewer:  L.Lesniak
Classif.:  * 05C35 Extremal problems (graph theory)
                   05C55 Generalized Ramsey theory
                   05C05 Trees
Keywords:  arboricity; sequence of graphs; largest independent set
Citations:  Zbl.253.05145

© 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