A note on matchings and co-matchings in bipartite graphs

Abstract

A class of bipartite graphs is said to have the strong Erdős-Hajnal property if there exists $\epsilon >0$ such that every graph $((A,B),E)$ in the class contains a complete or empty induced subgraph with parts $X\subseteq A$, $Y\subseteq B$ where $|X|\ge \epsilon |A|$ and $|Y|\ge \epsilon |B|$. Scott, Seymour and Spirkl proved that it is enough to forbid a forest and the bipartite complement of a forest. In this paper, we provide quantitative bounds on $\epsilon$ when we restrict to matchings.