论文标题
几乎所有最佳彩色完整图都包含彩虹汉密尔顿路径
Almost all optimally coloured complete graphs contain a rainbow Hamilton path
论文作者
论文摘要
如果$ h $的所有边缘都有不同的颜色，则一个边彩色图的子图$ h $称为彩虹。 1989年，安德森（Andersen）猜想，$ k_ {n} $的每一个适当的边缘色都承认了一条长度$ n-2 $的彩虹路径。我们表明，几乎所有$ k_ {n} $的最佳边缘都可以接受（i）彩虹汉密尔顿路径和（ii）使用所有颜色的彩虹循环。该结果表明，安德森的猜想几乎对$ k_ {n} $的几乎所有最佳边缘色都有，并回答了Ferber，Jain和Sudakov的最新问题。我们的结果还针对随机对称拉丁正方形的横向存在应用。
A subgraph $H$ of an edge-coloured graph is called rainbow if all of the edges of $H$ have different colours. In 1989, Andersen conjectured that every proper edge-colouring of $K_{n}$ admits a rainbow path of length $n-2$. We show that almost all optimal edge-colourings of $K_{n}$ admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of $K_{n}$ and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
