### 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 | |

State | Published - 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

Chudnovsky, M., & Oum, S. I. (2018). Vertex-minors and the Erdős–Hajnal conjecture.

*Discrete Mathematics*,*341*(12), 3498-3499. https://doi.org/10.1016/j.disc.2018.09.007