Vertex-minors and the Erdős–Hajnal conjecture

Maria Chudnovsky, Sang il Oum

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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
Volume341
Issue number12
DOIs
StatePublished - Dec 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Erdős–Hajnal conjecture
  • Vertex-minor

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

  • Cite this