Rainbow matchings in bipartite multigraphs

Suppose that $k$ is a non-negative integer and a bipartite multigraph $G$ is the union of $N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1)$ matchings $M_1,\dots,M_N$, each of size $n$. We show that $G$ has a rainbow matching of size $n-k$, i.e. a matching of size $n-k$ with all edges coming from different $M_i$'s. Several choices of parameters relate to known results and conjectures.

No reviews yet.

No comments yet.