Rainbow cycles versus rainbow paths

Anastasia Halfpap, Cory Palmer

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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 languageEnglish
Pages (from-to)152-169
Number of pages18
JournalAustralasian Journal of Combinatorics
StatePublished - 2021


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.

FundersFunder number
Simons Foundation712036


    Dive into the research topics of 'Rainbow cycles versus rainbow paths'. Together they form a unique fingerprint.

    Cite this