Excluding Hooks and their Complements

Abstract

The long-standing Erdős-Hajnal conjecture states that for every $n$-vertex undirected graph $H$ there exists $\epsilon(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or an independent set of size at least $n^{\epsilon(H)}$. A natural weakening of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both $H$ and its complement $H^\mathrm{c}$. These conjectures have been shown to hold for only a handful of graphs: it is not even known if they hold for all graphs on $5$ vertices.

In a recent breakthrough, the symmetrized version of the Erdős-Hajnal conjecture was shown to hold for all paths. The goal of this paper is to show that the symmetrized conjecture holds for all trees on $6$ (or fewer) vertices. In fact this is a consequence of showing that the symmetrized conjecture holds for any path with a pendant edge at its third vertex; thus we also give a new infinite family of graphs for which the symmetrized conjecture holds.