Excluding hooks and their complements (Q1671647)

Summary: The long-standing Erdős-Hajnal conjecture states that for every \(n\)-vertex undirected graph \(H\) there exists \(\varepsilon(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^{\varepsilon(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^{\text{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.