Multicolor Turán numbers

DOI10.1016/J.DISC.2022.112976zbMath1491.05082arXiv2110.02367OpenAlexW4280575053MaRDI QIDQ2144522

András Imolay, Benedek Váli, János Karl, Zoltán Lóránt Nagy

Publication date: 14 June 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider a natural generalisation of Tur'an's forbidden subgraph problem and the Ruzsa-Szemer'edi problem by studying the maximum number $e{x}_F(n,G)$ of edge-disjoint copies of a fixed graph $F$ can be placed on an $n$-vertex ground set without forming a subgraph $G$ whose edges are from different $F$-copies. We determine the pairs $F,G$ for which the order of magnitude of $e{x}_F(n,G)$ is quadratic and prove several asymptotic results using various tools from the regularity lemma and supersaturation to graph packing results.

Full work available at URL: https://arxiv.org/abs/2110.02367

zbMATH Keywords

extremal graphsregularity lemmagraph packingmulticolor

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On 3-uniform hypergraphs without a cycle of a given length
• On the maximum number of five-cycles in a triangle-free graph
• Supersaturated graphs and hypergraphs
• Integer and fractional packings in dense graphs
• Pentagons vs. triangles
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
• Multicolour Turán problems
• The minimum independence number for designs
• On the number of pentagons in triangle-free graphs
• Turán numbers for Berge-hypergraphs and related extremal problems
• A linear hypergraph extension of the bipartite Turán problem
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Hypergraphs with No Cycle of a Given Length
• Rainbow Turán Problems
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• Note on independent sets in steiner systems
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• A note on the maximum number of triangles in a C₅‐free graph
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• The History of Degenerate (Bipartite) Extremal Graph Problems
• On the structure of linear graphs

Related Items (2)

On multicolor Turán numbers ⋮ Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles

This page was built for publication: Multicolor Turán numbers