Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
复制标题
DOI：
10.1016/j.ejc.2019.02.008
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
J. Balogh;T. Molla
中科院分区：
文献类型：
--
作者：
J. Balogh;T. Molla
我们证明了关于真边着色图中圈的两个结果。首先，我们对Alon，Pokrovski和Sudakov最近的突破性工作做了一点小的改进，证明了n个顶点上的每个真边色完全图G在至少n个−O(n 3/4)个顶点上都有彩虹圈，从而证明了G在至少n个−O(Logn N)个顶点上有彩虹圈。其次，通过修改Hatami和Shor关于拉丁方图中部分横截长度的下界的论点，我们证明了每一个适当着色的完全图都有一个哈密顿圈，其中至少有n个−O((Logn)2)不同的颜色出现。对于大的n，这是对Andersen的n−2n的已知下界的改进。
We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed that every properly edge-colored complete graph G on n vertices has a rainbow cycle on at least n− O (n 3∕ 4) vertices, by showing that G has a rainbow cycle on at least n− O (log n n) vertices. Second, by modifying the argument of Hatami and Shor which gives a lower bound for the length of a partial transversal in a Latin Square, we prove that every properly colored complete graph has a Hamiltonian cycle in which at least n− O ((log n) 2) different colors appear. For large n, this is an improvement of the previous best known lower bound of n− 2 n of Andersen.