2019/11/15 by Dániel Gerbner, Gerbner, Dániel, Tamás Mészáros +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1911.06642
openalex publication_date 2019/11/15 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
Alon and Shikhelman 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. 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.