|国家预印本平台
首页|Almost-perfect colorful matchings in three-edge-colored bipartite graphs

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

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

来源:Arxiv_logoArxiv
英文摘要

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\"uyesser, and Szab\'o, for three colors.

Simona Boyadzhiyska、Micha Christoph、Tibor Szabó

数学

Simona Boyadzhiyska,Micha Christoph,Tibor Szabó.Almost-perfect colorful matchings in three-edge-colored bipartite graphs[EB/OL].(2025-04-21)[2025-05-07].https://arxiv.org/abs/2504.15167.点此复制

评论