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

Josefran de Oliveira Bastos, Hanno Lefmann, Andy Oertel, Carlos Hoppen, Dionatan Ricardo Schmidt
Discrete Applied Mathematics, 2023
Journal version of "Maximum number of \( r \)-edge-colorings such that all copies of \( K_k \) are rainbow"



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.