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 -