An extension of the rainbow Erdős-Rothschild problem

Abstract

Given integers $r\ge 2$, $k\ge 3$ and $2\le s\le \left(\genfrac{}{}{0ex}{}{k}{2}\right)$, and a graph $G$, we consider $r$-edge-colorings of $G$ with no copy of a complete graph $K_k$ on $k$ vertices where $s$ or more colors appear, which are called ${\mathcal{P}}_{k,s}$-free $r$-colorings. We show that, for large $n$ and $r\ge r_0(k,s)$, the $(k-1)$-partite Turán graph $T_{k-1}(n)$ on $n$ vertices yields the largest number of ${\mathcal{P}}_{k,s}$-free $r$-colorings among all $n$-vertex graphs, and that it is the unique graph with this property.