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

We consider a version of the Erdos-Rothschild problem for families of graph patterns. For any fixed k > 3, let r0(k) be the largest integer such that the following holds for all 2 < r < r0(k) and all sufficiently large n: The Turan graph Tk-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 Kk in G is rainbow. We use the regularity lemma of Szemeredi and linear programming to obtain a lower bound on the value of r0(k). For a more general family P of patterns of Kk, we also prove that, in order to show that the Turan graph Tk-1(n) maximizes the number of P-free r-edge-colorings over n-vertex graphs, it suffices to prove a related stability result.(c) 2023 Elsevier B.V. All rights reserved.