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