The generalised rainbow Turán problem for cycles

Given an edge-coloured graph, we say that a subgraph is rainbow if all of its edges have different colours. Let $\operatorname{ex}(n,H,$rainbow-$F)$ denote the maximal number of copies of $H$ that a properly edge-coloured graph on $n$ vertices can contain if it has no rainbow subgraph isomorphic to $F$. We determine the order of magnitude of $\operatorname{ex}(n,C_s,$rainbow-$C_t)$ for all $s,t$ with $s\not =3$. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer by showing that $\operatorname{ex}(n,C_{2k},$rainbow-$C_{2k})$ is $Θ(n^{k-1})$ if $k\geq 3$ and $Θ(n^2)$ if $k=2$. We also determine the order of magnitude of $\operatorname{ex}(n,P_\ell,$rainbow-$C_{2k})$ for all $k,\ell\geq 2$, where $P_\ell$ denotes the path with $\ell$ edges.

No reviews yet.

No comments yet.