On multicolor Turán numbers

2024/02/07 by József Balogh, Anita Liebenau, Balogh, József +5
Computer Science · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2402.05060

openalex publication_date 2024/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We address a problem which is a generalization of Turán-type problems recently introduced by Imolay, Karl, Nagy and Váli. Let F be a fixed graph and let G be the union of k edge-disjoint copies of F, namely G = \mathbin∪_i=1^k F_i, where each F_i is isomorphic to a fixed graph F and E(F_i)∩ E(F_j)=∅ for all i ≠ j. We call a subgraph H⊆ G multicolored if H and F_i share at most one edge for all i. Define ex_F(H,n) to be the maximum value k such that there exists G = \mathbin∪_i=1^k F_i on n vertices without a multicolored copy of H. We show that ex_C5(C₃,n) ≤ n²/25 + 3n/25+o(n) and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.

Related

• Multicolor Turán numbers
• On the multicolor Turán conjecture for color-critical graphs
• On F-multicolor Turán number of hypergraph graphs
• Multicolor Turán numbers II -- a generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
• On edges not in monochromatic copies of a fixed bipartite graph