Generalized rainbow Turán problems

Dániel Gerbner, Tamás Mészáros, Abhishek Methuku, Cory Palmer

Research output: Contribution to journalArticlepeer-review

Abstract

Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Turán problem: for fixed graphs H and F and an integer n, what is the maximum number of copies of H in an n-vertex F-free graph? An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Turán number of F is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of F . The study of rainbow Turán problems was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Comb. Probab. Comput. 16 (2007)]. Motivated by the above problems, we study the following problem: What is the maximum number of copies of F in a properly edge-colored graph on n vertices without a rainbow copy of F? We establish several results, including when F is a path, cycle or tree.

Original languageEnglish
Article number#P2.44
JournalElectronic Journal of Combinatorics
Volume29
Issue number2
DOIs
StatePublished - 2022

Fingerprint

Dive into the research topics of 'Generalized rainbow Turán problems'. Together they form a unique fingerprint.

Cite this