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$.
@article{10_37236_9536,
author = {Jaehoon Kim and Sang-il Oum},
title = {The {Erd\H{o}s-Hajnal} property for graphs with no fixed cycle as a pivot-minor},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {2},
doi = {10.37236/9536},
zbl = {1461.05143},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9536/}
}
TY - JOUR
AU - Jaehoon Kim
AU - Sang-il Oum
TI - The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9536/
DO - 10.37236/9536
ID - 10_37236_9536
ER -
%0 Journal Article
%A Jaehoon Kim
%A Sang-il Oum
%T The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9536/
%R 10.37236/9536
%F 10_37236_9536
Jaehoon Kim; Sang-il Oum. The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9536
