The Erdős-Hajnal conjecture for caterpillars and their complements

The celebrated Erdos-Hajnal conjecture states that for every proper hereditary graph class GG there exists a constant eps>0 such that every graph G in GG contains a clique or an independent set of size |V(G)|^eps. Recently, there has been a growing interest in the symmetrized variant of this conjecture, where one additionally requires GG to be closed under complementation. 

 

We show that any hereditary graph class that is closed under complementation and excludes a fixed caterpillar as an induced subgraph satisfies the Erdos-Hajnal conjecture. Here, a caterpillar is a tree whose vertices of degree at least three lie on a single path (i.e., our caterpillars may have arbitrarily long legs). In fact, we prove a stronger property of such graph classes, called in the literature the strong Erdos-Hajnal property: for every such graph class GG, there exists a constant delta>0 such that every graph G in GG contains two disjoint sets A,B of vertices of size at least delta*|V(G)| each so that either all edges between A and B are present in G, or none of them. This result significantly extends the family of graph classes for which we know that the strong Erdos-Hajnal property holds; for graph classes excluding a graph H and its complement it was previously known only for paths [Bousquet, Lagoutte, Thomasse, JCTB 2015] and hooks (i.e., paths with an additional pendant vertex at third vertex of the path) [Choromanski, Falik, Liebenau, Patel, Pilipczuk, arXiv:1508.00634]. The result and used techniques also show close relation of the topic with the celebrated Gyarfas-Sumner conjecture on chi-boundedness of graph classes excluding a fixed tree as an induced subgraph.