Article ID Journal Published Year Pages File Type
4653871 European Journal of Combinatorics 2013 11 Pages PDF
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
, , ,