For every fixed graph $H$, if a graph $G$ does not contain $H$ as a minor, then one can say a lot about the structure and properties of $H$. Unfortunately, results of that kind do not seem to be true if we replace the minor containment by induced subgraph containment. One of the few conjectures about general behavior of graphs with certain induced subgraphs forbidden is the Erdos Hajnal Conjecture. It states that for every fixed graph $H$ there exists a constant $\delta(H)$, such that if a graph $G$ has no induced subgraph isomorphic to $H$, then $G$ contains a big clique or a big stable set of size $|V(G)|^\delta(H)$.
The Erdos Hajal Conjecture is known to be true for graphs $H$ on at most four vertices, but there are some five-vertex graphs for which the conjecture is still open. One of such graphs is a path of length four (edges). We prove that if a graph $G$ does not contain as induced subgraphs a path of length four or the complement of a path of length five, then $G$ contains a clique or a stable set of size $|V(G)|^{\frac{1}{6}}$.
This is joint work with Yori Zwols.
Copyright. All Rights Reserved.