Multicolor Turán numbers

Abstract

We consider a natural generalisation of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi 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.