Large cliques or stable sets in graphs with no $P_4$ and no $P_5^c$
<-- Return to the list
Date: 04-21-2009
Start Time:
5:30pm
End Time: 6:30pm
Speaker: Yori Zwols, Industrial Engineering & Operations Research: Columbia University
Location: 507 Math
ABSTRACT
Erdos and Hajnal 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^e(H)$ for some $e(H) > 0$. The conjecture is known to be true for graphs $H$ on at most four vertices. 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 paper 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/8}$.
This is joint work with Maria Chudnovsky.