Rainbow cycles versus rainbow paths

Anastasia Halfpap, Cory Palmer

Research output: Contribution to journalArticlepeer-review

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

Fingerprint

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

Cite this