Rainbow cycles vs. rainbow paths

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á...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-08
Main Authors: Halfpap, Anastasia, Palmer, Cory
Format: Article
Language:English
Subjects:
Graph coloring
Graph theory
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422