Graphs with many edge-colorings such that complete graphs are rainbow
We consider a version of the Erdős–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 Turán 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