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