pith. sign in

arxiv: 1804.11008 · v2 · pith:RPIWTQ4Cnew · submitted 2018-04-30 · 🧮 math.CO

Vertex-minors and the ErdH{o}s-Hajnal conjecture

classification 🧮 math.CO
keywords vertex-minorsconjectureeverygraphs-hajnalvarepsilonanaloganticomplete
0
0 comments X
read the original abstract

We prove that for every graph $H$, there exists $\varepsilon>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|\ge \varepsilon 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.