Badges and rainbow matchings

Abstract

Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$. For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-1$ matchings suffice when $n$ is even). The known graphs showing sharpness of this conjecture for $n$ even are called badges. We improve the previously best known bound from $3n-2$ to $3n-3$, using a new line of proof that involves analysis of the appearance of badges. We also prove a "cooperative" generalization: for $t>0$ and $n\ge 3$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have a rainbow matching of size $n$.

Accepted for publication in Discrete Mathematics. 19 pages, 2 figures