## 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 C4 spans K4. (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 K4-e. In this paper it is proved that if G contains no induced C4 and K4-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