Suppose that $R$ (red) and $B$ (blue) are two graphs on the same vertex set of size $n$, and $H$ is some graph with a red-blue coloring of its edges. How large can $R$ and $B$ be if $Rcup B$ does not contain a copy of $H$? Call the largest such integer $mathrm{mex}(n, H)$. This problem was introduced by Diwan and Mubayi, who conjectured that (except for a few specific exceptions) when $H$ is a complete graph on $k+1$ vertices with any coloring of its edges $mathrm{mex}(n,H)=mathrm{ex}(n, K_{k+1})$. This conjecture generalizes Turans theorem. Diwan and Mubayi also asked for an analogue of ErdH{o}s-Stone-Simonovits theorem in this context. We prove the following asymptotic characterization of the extremal threshold in terms of the chromatic number $chi(H)$ and the textit{reduced maximum matching number} $mathcal{M}(H)$ of $H$. $$mathrm{mex}(n, H)=left(1- frac{1}{2(chi(H)-1)} - Omegaleft(frac{mathcal{M}(H)}{chi(H)^2}right)right)frac{n^2}{2}.$$ $mathcal{M}(H)$ is, among the set of proper $chi(H)$-colorings of $H$, the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than $2$ colors and is tight up to the implied constant factor. We also study $mathrm{mex}(n, H)$ when $H$ is a cycle with a red-blue coloring of its edges, and we show that $mathrm{mex}(n, H)lesssim frac{1}{2}binom{n}{2}$, which is tight.
Download