Rainbow cycles vs. rainbow paths

• Published in: arXiv.org 2020-08
• Main Authors: Halfpap, Anastasia, Palmer, Cory
• Format: Article
• Language: English
• Subjects: Graph coloring; Graph theory; Upper bounds
• ISSN: 2331-8422

An edge-colored graph \(F\) is {\it rainbow} if each edge of \(F\) has a unique color. The {\it rainbow Turán number} \(\mathrm{ex}^*(n,F)\) of a graph \(F\) is the maximum possible number of edges in a properly edge-colored \(n\)-vertex graph with no rainbow copy of \(F\). The study of rainbow Turán numbers was introduced by Keevash, Mubayi, Sudakov, and Verstra\"ete. Johnson and Rombach introduced the following rainbow-version of generalized Turán problems: for fixed graphs \(H\) and \(F\), let \(\mathrm{ex}^*(n,H,F)\) denote the maximum number of rainbow copies of \(H\) in an \(n\)-vertex properly edge-colored graph with no rainbow copy of \(F\). In this paper we investigate the case \(\mathrm{ex}^*(n,C_\ell,P_\ell)\) and give a general upper bound as well as exact results for \(\ell = 3,4,5\). Along the way we establish a new best upper bound on \(\mathrm{ex}^*(n,P_5)\). Our main motivation comes from an attempt to improve bounds on \(\mathrm{ex}^*(n,P_\ell)\), which has been the subject of several recent manuscripts.