Abstract
An edge-colored graph F is rainbow if each edge of F has a unique color. The rainbow Tur´an number 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´an numbers was introduced by Keevash, Mubayi, Sudakov, and Verstra¨ete in 2007. Johnson and Rombach introduced the following rainbow-version of generalized Tur´an problems: For fixed graphs H and F, let 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 ex*(n,C, P) and give a general upper bound as well as exact results for = 3, 4, 5. Along the way we establish a new best upper bound on ex*(n, P5). Our main motivation comes from an attempt to improve bounds on ex*(n, P), which has been the subject of several recent papers.
Original language | English |
---|---|
Pages (from-to) | 152-169 |
Number of pages | 18 |
Journal | Australasian Journal of Combinatorics |
Volume | 81 |
State | Published - 2021 |
Funding
We thank the anonymous referees for their careful reading of the manuscript and, among other things, for pointing out that uniqueness can be proved in Theorem 3.1. The second author’s research was supported by a grant from the Simons Foundation #712036.
Funders | Funder number |
---|---|
Simons Foundation | 712036 |