Maximum number of edge colorings avoiding rainbow copies of $K_4$

Abstract

In this paper we show that for $r\ge 12$ and any sufficiently large $n$-vertex graph $G$ the number of $r$-edge-colorings of $G$ with no rainbow $K_4$ is at most $r^{ex(n,K_4)}$, where $ex(n,K_4)$ denotes the Turán number of $K_4$. Moreover, $G$ attains equality if and only if it is the Turán graph $T_3(n)$. The bound on the number of colors $r\ge 12$ is best possible. It improves upon a result of H. Lefmann, D.A. Nolibos, and the second author who showed the same result for $r\ge 5434$ and it confirms a conjecture by Gupta, Pehova, Powierski and Staden.

15 pages