pith. machine review for the scientific record. sign in

arxiv: 1202.3221 · v2 · submitted 2012-02-15 · 🧮 math.CO

Recognition: unknown

Rainbow Tur\'an Problem for Even Cycles

Authors on Pith no claims yet
classification 🧮 math.CO
keywords rainbowvarepsilongraphedge-colorededgesevennumbercycle
0
0 comments X
read the original abstract

An edge-colored graph is rainbow if all its edges are colored with distinct colors. For a fixed graph $H$, the rainbow Tur\'an number $\mathrm{ex}^{\ast}(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\'an number of even cycles, and prove that for every fixed $\varepsilon > 0$, there is a constant $C(\varepsilon)$ such that every properly edge-colored graph on $n$ vertices with at least $C(\varepsilon) n^{1 + \varepsilon}$ edges contains a rainbow cycle of even length at most $2 \lceil \frac{\ln 4 - \ln \varepsilon}{\ln (1 + \varepsilon)} \rceil$. This partially answers a question of Keevash, Mubayi, Sudakov, and Verstra\"ete, who asked how dense a graph can be without having a rainbow cycle of any length.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.