Rainbow cycles versus rainbow paths

Anastasia Halfpap, Cory Palmer

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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

FundersFunder number
Simons Foundation712036

    Fingerprint

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

    Cite this