Rainbow Turán problem for even cycles
Rainbow Turán problem for even cycles
复制标题
偶数周期彩虹图兰问题
DOI：
10.1016/j.ejc.2013.01.003
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Shagnik Das;Choongbum Lee;B. Sudakov
一个边着色图是彩虹图，如果它的所有边都用不同的颜色着色。对于固定图H，彩虹图兰数ex_n（n，H）定义为n个顶点的正确边着色图中的最大边数，且没有H的彩虹副本.本文研究了偶数圈的彩虹图兰数，证明了对任意固定的ε>0，存在一个常数C（ε），使得任意n个顶点上的边数至少为C（ε）n1+ε的正常边着色图都包含一个长度至多为2的偶数彩虹圈.这部分回答了Keevash、Mubayi、Sudakov和Verstraëte的一个问题，他们问一个图在没有任何长度的彩虹周期的情况下可以有多密集。
An edge-colored graph is rainbow if all its edges are colored with distinct colors. For a fixed graph H, the rainbow Turán number ex∗(n,H) is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of H. We study the rainbow Turán number of even cycles, and prove that for every fixed ε>0, there is a constant C(ε) such that every properly edge-colored graph on n vertices with at least C(ε)n1+εedges contains a rainbow cycle of even length at most 2⌈ln4−lnεln(1+ε)⌉. This partially answers a question of Keevash, Mubayi, Sudakov, and Verstraëte, who asked how dense a graph can be without having a rainbow cycle of any length.