\input zb-basic
\input zb-ioport
\iteman{io-port 06074826}
\itemau{Chudnovsky, Maria; Zwols, Yori}
\itemti{Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement.}
\itemso{J. Graph Theory 70, No. 4, 449-472 (2012).}
\itemab
Summary: {\it P. Erd\H{o}s} and {\it A. Hajnal} [Discrete Appl. Math. 25, No. 1--2, 37--52 (1989; Zbl 0715.05052)] conjectured that, for any graph $H$, every graph on $n$ vertices that does not have $H$ as an induced subgraph contains a clique or a stable set of size $n^{\varepsilon (H)}$ for some $\varepsilon (H)>0$. The Conjecture 1. known to be true for graphs $H$ with $|V(H)|\leq 4$. One of the two remaining open cases on five vertices is the case where $H$ is a four-edge path, the other case being a cycle of length five. In this article we prove that every graph on $n$ vertices that does not contain a four-edge path or the complement of a five-edge path as an induced subgraph contains either a clique or a stable set of size at least $n^{1/6}$.
\itemrv{~}
\itemcc{}
\itemut{Erd\H{o}s-Hajnal conjecture; forbidden induced subgraphs}
\itemli{doi:10.1002/jgt.20626}
\end