Vertex-minors and the Erdős–Hajnal conjecture

Maria Chudnovsky; Sang il Oum

doi:10.1016/j.disc.2018.09.007

Vertex-minors and the Erdős–Hajnal conjecture

Maria Chudnovsky, Sang il Oum

Mathematics

Research output: Contribution to journal › Article › peer-review

6 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 language	English (US)
Pages (from-to)	3498-3499
Number of pages	2
Journal	Discrete Mathematics
Volume	341
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2018.09.007
State	Published - Dec 2018

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Erdős–Hajnal conjecture
Vertex-minor

Access to Document

10.1016/j.disc.2018.09.007

Cite this

@article{01a2cd338c5f468c9b796d5cebc42586,

title = "Vertex-minors and the Erd{\H o}s–Hajnal conjecture",

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{\H o}s–Hajnal conjecture for vertex-minors.",

keywords = "Erd{\H o}s–Hajnal conjecture, Vertex-minor",

author = "Maria Chudnovsky and Oum, {Sang il}",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = dec,

doi = "10.1016/j.disc.2018.09.007",

language = "English (US)",

volume = "341",

pages = "3498--3499",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Vertex-minors and the Erdős–Hajnal conjecture

AU - Chudnovsky, Maria

AU - Oum, Sang il

PY - 2018/12

Y1 - 2018/12

N2 - 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.

AB - 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.

KW - Erdős–Hajnal conjecture

KW - Vertex-minor

UR - http://www.scopus.com/inward/record.url?scp=85053924305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053924305&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2018.09.007

DO - 10.1016/j.disc.2018.09.007

M3 - Article

AN - SCOPUS:85053924305

SN - 0012-365X

VL - 341

SP - 3498

EP - 3499

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

Vertex-minors and the Erdős–Hajnal conjecture

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this