Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  511.05047
Autor:  Erdös, Paul; Pach, János
Title:  On a quasi-Ramsey problem. (In English)
Source:  J. Graph Theory 7, 137-147 (1983).
Review:  The authors define Rt(n) as the smallest natural number R such that, for any graph G of order R, either G or the complement of G contains a subgraph H of order at least n and minimum degree at least t|V(H)|. They show that for each fixed t > ½ , the function Rt(n) increases exponentially whereas it is bounded above by a linear function for each fixed t < ½ . Finally, they show that R ½(n) < cn log n and that this is close to best possible.
Reviewer:  C.Thomassen
Classif.:  * 05C55 Generalized Ramsey theory
                   60C05 Combinatorial probability
Keywords:  complement of graph; subgraph; minimum degree

© 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