WikiEdge:ArXiv-2409.03623v1/abs

编辑

• 标题：A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers
• 中文标题：埃尔德什和贾尔法斯关于单色路径覆盖的猜想的证明
• 发布日期：2024-09-05T15:34:53+00:00
• 作者：Alexey Pokrovskiy, Leo Versteegen, Ella Williams
• 分类：math.CO
• 原文链接：http://arxiv.org/abs/2409.03623v1

摘要：在1995年，Erdős和Gyárfás证明了在每个$n$个顶点的$2$边着色完全图中，存在一组$2\sqrt{n}$条同色的单色路径，覆盖整个顶点集。他们猜测可以将$2\sqrt{n}$替换为$\sqrt{n}$。我们证明这一点对于所有足够大的$n$是成立的。