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

Abstract

The celebrated Erdős-Hajnal conjecture states that for every proper hereditary graph class $\mathcal{G}$ there exists a constant $\epsilon =\epsilon (\mathcal{G})>0$ such that every graph $G\in \mathcal{G}$ contains a clique or an independent set of size $|V(G){|}^{\epsilon }$. Recently, there has been a growing interest in the symmetrized variant of this conjecture, where one additionally requires $\mathcal{G}$ 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 Erdős-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 Erdős-Hajnal property: for every such graph class $\mathcal{G}$, there exists a constant $\delta =\delta (\mathcal{G})>0$ such that every graph $G\in \mathcal{G}$ contains two disjoint sets $A,B\subseteq V(G)$ 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 Erdős-Hajnal property holds; for graph classes excluding a graph $H$ and its complement it was previously known only for paths [Bousquet, Lagoutte, Thomassé, 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].

References in corpus (1)

• Clique-Stable Set separation in perfect graphs with no balanced skew-partitions