The Erdős-Hajnal conjecture for caterpillars and their complements
share
The celebrated Erdős-Hajnal conjecture states that for every proper hereditary graph class G there exists a constant ε = ε(G) > 0 such that every graph G ∈G contains a clique or an independent set of size |V(G)|^ε. Recently, there has been a growing interest in the symmetrized variant of this conjecture, where one additionally requires 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 G, there exists a constant δ = δ(G) > 0 such that every graph G ∈G contains two disjoint sets A,B ⊆ V(G) of size at least δ|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].
READ FULL TEXT