Generalized rainbow Turán numbers of odd cycles

2020/10/27 by József Balogh, Balogh, József, Michelle Delcourt +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2010.14609

arxiv created 2021/09/21 · arxiv updated 2021/09/23

Abstract

Given graphs F and H, the generalized rainbow Turán number ex(n,F,rainbow-H) is the maximum number of copies of F in an n-vertex graph with a proper edge-coloring that contains no rainbow copy of H. B. Janzer determined the order of magnitude of ex(n,C_s,rainbow-C_t) for all s≥ 4 and t≥ 3, and a recent result of O. Janzer implied that ex(n,C₃,rainbow-C_2k)=O(n^1+1/k). We prove the corresponding upper bound for the remaining cases, showing that ex(n,C₃,rainbow-C_2k+1)=O(n^1+1/k). This matches the known lower bound for k even and is conjectured to be tight for k odd.

Related

• Rainbow cycles vs. rainbow paths
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Generalized rainbow Turán problems
• Rainbow Turán Problem for Even Cycles
• Maximum packings in graphs forbidding given rainbow cycles