Vertex-minors and the Erdős–Hajnal conjecture

Maria Chudnovsky, Sang il Oum

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We prove that for every graph H, there exists ε>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 |A|,|B|≥ε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 Erdős–Hajnal conjecture for vertex-minors.

Original languageEnglish (US)
Pages (from-to)3498-3499
Number of pages2
JournalDiscrete Mathematics
Issue number12
StatePublished - Dec 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


  • Erdős–Hajnal conjecture
  • Vertex-minor


Dive into the research topics of 'Vertex-minors and the Erdős–Hajnal conjecture'. Together they form a unique fingerprint.

Cite this