On multicolor Turán numbers

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={\dot{\cup }}_{i=1}^k{F}_i$, where each $F_i$ is isomorphic to a fixed graph $F$ and $E(F_i)\cap E(F_j)=\varnothing$ for all $i\ne j$. We call a subgraph $H\subseteq G$ multicolored if $H$ and $F_i$ share at most one edge for all $i$. Define ${\text{ex}}_F(H,n)$ to be the maximum value $k$ such that there exists $G={\dot{\cup }}_{i=1}^k{F}_i$ on $n$ vertices without a multicolored copy of $H$. We show that ${\text{ex}}_{C_5}(C_3,n)\le n^2/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.

17 pages