## Graphs with many edge-colorings such that complete graphs are rainbow

*2023*

**Journal version of "Maximum number of \( r \)-edge-colorings such that all copies of \( K_k \) are rainbow"**

Josefran de Oliveira Bastos, Hanno Lefmann, Andy Oertel, Carlos Hoppen, Dionatan Ricardo Schmidt

Discrete Applied Mathematics, *2023*

We consider a version of the Erdős-Rothschild problem for families of graph patterns. For any fixed \( k \geq 3 \), let \( r_0(k) \) be the largest integer such that the following holds for all \( 2 \leq r \leq r_0(k) \) and all sufficiently large \( n \): The Turán graph \( T_{k−1}(n) \) is the unique \( n \)-vertex graph \( G \) with the maximum number of \( r \)-edge-colorings such that the edge set of any copy of \( K_k \) in \( G \) is rainbow. We use the regularity lemma of Szemerédi and linear programming to obtain a lower bound on the value of \( r_0(k) \). For a more general family \( \mathcal{P} \) of patterns of \( K_k \), we also prove that, in order to show that the Turán graph \( T_{k−1}(n) \) maximizes the number of \( \mathcal{P} \)-free \( r \)-edge-colorings over \( n \)-vertex graphs, it suffices to prove a related stability result.