Graphs in which each \(C_4\) spans \(K_4\) (Q1918557)

This paper concerns a conjecture of the {P.~Erdős} and \textit{A.~Hajnal} [Discrete Appl. Math. 25, No. 1/2, 37-52 (1989; Zbl 0715.05052)] that for each graph \(H\) there exists a positive constant \(\varepsilon= \varepsilon(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 \(\varepsilon= 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.