Towards Erdős-Hajnal property for dp-minimal graphs

Abstract

We introduce the notion of strongly $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$-free graphs, which contain dp-minimal graphs. We show that under some sparsity assumption, given a rainbow $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$-free blockade we can find a rainbow $\left(\genfrac{}{}{0ex}{}{k-1}{2}\right)$-free blockade. This might serve as an intermediate step towards Erd\H os-Hajnal property for dp-minimal graphs.

Things after the main lemma (lemma 3.4) in version 1 were deleted since the argument after that was a misuse of Rodl's theorem. The author still needs to remove the sparsity assumption in order to get Erd\H os-Hajnal property for dp-minimal graphs. Also reference mistakes were fixed in version 2