vix.ing · top · new · best · stats · spec

A note on matchings and co-matchings in bipartite graphs

2026/07/27 by Sida Li
#math.CO

paper · pdf

Abstract

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

Citations

Related