Almost-perfect colorful matchings in three-edge-colored bipartite graphs
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 $2n$ 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.
Publication Details
- Journal
- ArXiv.org
- Published
- 2025-04-21
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Engineering and Physical Sciences Research Council