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\ge 4$, every $(n,3n-2)$-multigraph contains a rainbow matching of size $n$. Here, we prove the conjecture for all sufficiently large $n$.