Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653871 | European Journal of Combinatorics | 2013 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Shagnik Das, Choongbum Lee, Benny Sudakov,