The ErdH{o}s-Hajnal property for graphs with no fixed cycle as a pivot-minor


الملخص بالإنكليزية

We prove that for every integer $k$, there exists $varepsilon > 0$ such that for every n-vertex graph $G$ with no pivot-minor isomorphic to $C_k$, there exist disjoint sets $A,B subseteq V(G)$ such that $|A|,|B| geq varepsilon n$, and $A$ is either complete or anticomplete to $B$. This proves the analog of the ErdH{o}s-Hajnal conjecture for the class of graphs with no pivot-minor isomorphic to $C_k$.

تحميل البحث