Large matchings in bipartite graphs have a rainbow matching

Abstract

Let $g(n)$ be the least number such that every collection of $n$ matchings, each of size at least $g(n)$, in a bipartite graph, has a full rainbow matching. Aharoni and Berger \cite{AhBer} conjectured that $g(n)=n+1$ for every $n>1$. This generalizes famous conjectures of Ryser, Brualdi and Stein. Recently, Aharoni, Charbit and Howard \cite{ACH} proved that $g(n)\le \lfloor \frac{7}{4}n\rfloor$. We prove that $g(n)\le \lfloor \frac{5}{3}n\rfloor$.

References in corpus (1)

• Rainbow matchings and partial transversals of Latin squares