Pivot-minors and the Erdős-Hajnal conjecture

Abstract

We prove a conjecture of Kim and Oum that every proper pivot-minor-closed class of graphs has the strong Erdős-Hajnal property. More precisely, for every graph $H$, there exists $\epsilon >0$ such that every $n$-vertex graph with no pivot-minor isomorphic to $H$ contains two sets $A,B$ of vertices such that $|A|,|B|\ge \epsilon n$ and $A$ is complete or anticomplete to $B$.

arXiv comment18 pages