##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 854.05061

**Autor: ** Erdös, Paul; Gyárfás, András; Luczak, Tomasz

**Title: ** Graphs in which each C_{4} spans K_{4}. (In English)

**Source: ** Discrete Math. 154, No.1-3, 263-268 (1996).

**Review: ** This paper concerns a conjecture of the {P.~Erdös} and {\it A.~Hajnal} [Discrete Appl. Math. 25, No. ½, 37-52 (1989; Zbl 715.05052)] that for each graph H there exists a positive constant \epsilon = \epsilon(H) with the property that every graph G on n vertices that does not contain an induced H has a homogeneous set of at least n vertices. It is known that \epsilon = 1/3 works for H being the 4-cycle or K_{4}-e. In this paper it is proved that if G contains no induced C_{4} and K_{4}-e, and n \geq 6, then G contains a homogeneous set of at least \lceil\sqrt n\rceil vertices.

**Reviewer: ** M.Skoviera (Bratislava)

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** independent set; forbidden induced subgraph; homogeneous set

**Citations: ** Zbl 715.05052

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag