论文标题
彩虹路径和大彩虹匹配
Rainbow paths and large rainbow matchings
论文作者
论文摘要
前两位作者的一个猜想是，任何图中的$ n $ n $匹配都具有大小$ n-1 $的彩虹匹配。我们证明了$ \ frac {2} {3} n-1 $的下限，在琐碎的$ \ frac {1} {2} {2} n $上得到改善，并为HyperGraphs提供了类似的结果。对于$ \ {c_3，c_5 \} $ - 免费图形，对于不相交的匹配，我们获得了$ \ frac {3n} {4} {4} -o（1）$的下限。我们还讨论了彩虹交替路径上的猜想，如果True将产生$ N- \ sqrt {2n} $的下限。我们证明了此猜想的非替代（普通路径）版本。
A conjecture of the first two authors is that $n$ matchings of size $n$ in any graph have a rainbow matching of size $n-1$. We prove a lower bound of $\frac{2}{3}n-1$, improving on the trivial $\frac{1}{2}n$, and an analogous result for hypergraphs. For $\{C_3,C_5\}$-free graphs and for disjoint matchings we obtain a lower bound of $\frac{3n}{4}-O(1)$. We also discuss a conjecture on rainbow alternating paths, that if true would yield a lower bound of $n-\sqrt{2n}$. We prove the non-alternating (ordinary paths) version of this conjecture.
