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
LAGOS (Procedia Computer Science), 2021



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 \( 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 \( P \)-free \( r \)-edge-colorings over \( n \)-vertex graphs, it suffices to prove a related stability result.