Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.15167 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913963370872832 |
|---|---|
| author | Boyadzhiyska, Simona Christoph, Micha Szabó, Tibor |
| author_facet | Boyadzhiyska, Simona Christoph, Micha Szabó, Tibor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15167 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Almost-perfect colorful matchings in three-edge-colored bipartite graphs Boyadzhiyska, Simona Christoph, Micha Szabó, Tibor Combinatorics 05C70 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. |
| title | Almost-perfect colorful matchings in three-edge-colored bipartite graphs |
| topic | Combinatorics 05C70 |
| url | https://arxiv.org/abs/2504.15167 |