Pivot-minors and the Erd\H{o}s-Hajnal conjecture

arXiv2305.09133MaRDI QIDQ6510135FDOQ6510135

Authors: James E. Davies 

Abstract: We prove a conjecture of Kim and Oum that every proper pivot-minor-closed class of graphs has the strong ErdH{o}s-Hajnal property. More precisely, for every graph $H$, there exists $epsilon>0$ such that every $n$-vertex graph with no pivot-minor isomorphic to $H$ contains two sets $A,B$ of vertices such that $|A|,|B|geepsilonn$ and $A$ is complete or anticomplete to $B$.

This page was built for publication: Pivot-minors and the Erd\H{o}s-Hajnal conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510135)