Badges and rainbow matchings

Abstract

© 2021 Elsevier B.V. All rights reserved. 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 >= 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.