Proof of Grinblat's conjecture on rainbow matchings in multigraphs

Abstract

Many well-known problems in combinatorics can be reduced to finding a large rainbow structure in a certain edge-coloured multigraph. Two celebrated examples of this are Ringel's tree packing conjecture and Ryser's conjecture on transversals in Latin squares. In this paper, we answer such a question raised by Grinblat twenty years ago. Let an (n, v)-multigraph be an n-edge-coloured multigraph in which the edges of each colour span a disjoint union of non-trivial cliques that have in total at least v vertices. Grinblat conjectured that for all n >= 4, every (n, 3n - 2)-multigraph contains a rainbow matching of size n. Here, we prove this conjecture for all sufficiently large n.