Vertex-minors and the ErdH{o}s-Hajnal conjecture
classification
🧮 math.CO
keywords
vertex-minorsconjectureeverygraphs-hajnalvarepsilonanaloganticomplete
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.