Erdős-Hajnal beyond the five-vertex path

Abstract

The well-known Erdős-Hajnal conjecture states that for any graph $H$, there is a constant $c=c(H)>0$ such that every $n$-vertex graph $G$ with no induced copies of $H$ contains a clique or an independent set of size at least $n^c$. We prove that Erdős-Hajnal conjecture holds for two more graph classes-graphs with no induced copies of $E$-graph and graphs with no induced copies of Birds, where $E$-graph is the graph obtained from the five-vertex path by adding a pendent edge to the middle vertex of the path and Bird is the graph obtained from a bull by adding a pendent edge to one horn of the bull. Our results generalize the result of Nguyen, Scott and Seymour on the five-vertex path (Proceedings of London Mathematical Society 2026) and the result of Chudnovsky and Safra on the bull graph (Journal of Combinatorial Theory Series B 2008). The proof uses the iterative sparsification framework proposed by Nguyen, Scott and Seymour with our generalization. We first reduce, up to some technical condition, Erdős-Hajnal conjecture to a property called generlaized nice, which is a generalization of the ``nice'' property used in [T.~Nguyen, A.~Scott, and P.~Seymour. Induced subgraph density. VII. The five-vertex path. {\em Proceedings of the London Mathematical Society}, 132(3):e70133, 2026]. We ues Ramsey Theorem and a new idea for embedding graphs with no leaf vertices to prove that $E$-graph and Bird satisfy this technical condition. We then reduce the generalized nice property to a new property $(\ast )$. Finally, we show that $E$-graph and Bird graph satisfiy $(\ast )$. One key step in the proof is to prove, via defining appropriate equivalence relations, that certain auxiliary graph satisfies the Erdős-Hajnal conjecture.

33 pages, 9 figures