Large rainbow matchings in general graphs

Abstract

By a theorem of Drisko, any $2n-1$ matchings of size $n$ in a bipartite graph have a partial rainbow matching of size $n$. Inspired by discussion of Barát, Gyárfás and Sárközy, we conjecture that if $n$ is odd then the same is true also in general graphs, and that if $n$ is even then $2n$ matchings of size $n$ suffice. We prove that any $3n-2$ matchings of size $n$ have a partial rainbow matching of size $n$.

6 pages