##
**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 R_{t}(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 R_{t}(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