Vertex-minors and the Erdos-Hajnal conjecture

Abstract

We prove that for every graph H, there exists epsilon > 0 such that every n-vertex graph with no vertex-minors isomorphic to H has a pair of disjoint sets A, B of vertices such that vertical bar A vertical bar, vertical bar B vertical bar >= epsilon n and A is complete or anticomplete to B. We deduce this from recent work of Chudnovsky, Scott, Seymour, and Spirkl (2018). This proves the analog of the Erclas-Hajnal conjecture for vertex-minors. (C) 2018 Elsevier B.V. All rights reserved.