TY - JOUR

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

AU - Chudnovsky, Maria

AU - Oum, Sang il

N1 - Funding Information:
Chudnovsky was supported by National Science Foundation grant DMS-1550991 . This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-16-1-0404 . Oum was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2017R1A2B4005020 ).
Publisher Copyright:
© 2018 Elsevier B.V.

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 -