论文标题
徽章和彩虹比赛
Badges and rainbow matchings
论文作者
论文摘要
Drisko证明了$ 2N-1 $匹配的两部分尺寸$ n $的彩虹匹配尺寸$ n $。对于一般图，可以推测$ 2N $匹配的匹配功能足以满足此目的（并且$ n $偶数时，$ 2N-1 $匹配就足够了）。已知的图表显示了$ n $的猜想的清晰度，甚至称为徽章。我们使用新的证明线，涉及分析徽章的外观，从$ 3N-2 $提高了以前最著名的限制。我们还证明了“合作”的概括：对于$ t> 0 $和$ n \ geq 3 $，任何$ 3n-4+t $ set的边缘，每个$ t $的结合，其中包含$ n $的匹配，具有$ n $ $ n $的彩虹匹配。
Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$. For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-1$ matchings suffice when $n$ is even). The known graphs showing sharpness of this conjecture for $n$ even are called badges. We improve the previously best known bound from $3n-2$ to $3n-3$, using a new line of proof that involves analysis of the appearance of badges. We also prove a "cooperative" generalization: for $t>0$ and $n \geq 3$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have a rainbow matching of size $n$.
