Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets (Q6133146)

Summary: We study multigraphs whose edge-sets are the union of three perfect matchings, \(M_1, M_2\), and \(M_3\). Given such a graph \(G\) and any \(a_1,a_2,a_3\in \mathbb{N}\) with \(a_1+a_2+a_3\leq n-2\), we show there exists a matching \(M\) of \(G\) with \(|M\cap M_i|=a_i\) for each \(i\in \{1,2,3\}\). The bound \(n-2\) in the theorem is best possible in general. We conjecture however that if \(G\) is bipartite, the same result holds with \(n-2\) replaced by \(n-1\). We give a construction that shows such a result would be tight. We also make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour multiplicities.