The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor (Q2662350): Difference between revisions

Summary: 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\subseteq V(G)\) such that \(|A|,|B|\geqslant\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\).