Almost-perfect colorful matchings in three-edge-colored bipartite graphs

Simona Boyadzhiyska; Micha Christoph; Tibor Szabó

paper

Almost-perfect colorful matchings in three-edge-colored bipartite graphs

arXiv:2504.15167

Abstract

We prove that, for positive integers $n, a_{1}, a_{2}, a_{3}$ satisfying $a_{1} + a_{2} + a_{3} = n - 1$ , it holds that any bipartite graph $G$ which is the union of three perfect matchings $M_{1}$ , $M_{2}$ , and $M_{3}$ on $2 n$ vertices contains a matching $M$ such that $∣ M \cap M_{i} ∣ = a_{i}$ for $i = 1, 2,$ and $3$ . The bound $n - 1$ on the sum is best possible in general. Our result verifies the multiplicity extension of the Ryser-Brualdi-Stein Conjecture, proposed recently by Anastos, Fabian, Müyesser, and Szabó, for three colors.

16 pages