The Erdős-Hajnal Property for Graphs with No Fixed Cycle as a Pivot-Minor

Abstract

We prove that for every integer $k$, there exists $\varepsilon>0$ such that for every $n$-vertex graph with no pivot-minors isomorphic to $C_k$, there exist disjoint sets $A$, $B$ such that $|A|,|B|\ge\varepsilon n$, and $A$ is complete or anticomplete to $B$. This proves the analog of the Erdős-Hajnal conjecture for the class of graphs with no pivot-minors isomorphic to $C_k$.