Improved Bound on the Maximum Number of Clique-Free Colorings with Two and Three Colors

Given integers r, k >= 2 let k(r), (k+1)(G) denote the number of distinct edge colorings of G with r colors, which are Kk+1-free, i.e., which contain no monochromatic clique on k + 1 vertices. Alon et al. [J. Lond. Math. Soc. (2), 70 (2004), pp. 273-288] show that for r is an element of{2, 3} and all k >= 2 the maximum of k(r), (k+1)(G) over all G on n vertices is achieved only by the Turan graph, provided n > n(0)(k) is sufficiently large. The proof uses Szemeredi s regularity lemma and yields an n(0)(k) which is tower type with height exponential in k. As a lower bound the authors observed that n(0)(k) must be at least exponential in k. In this paper we essentially close the gap between the upper and the lower bound for n(0)(k). Answering the question posed by Alon et al. we show that the lower bound is of correct order and that it suffices to choose n(0)(k) = exp(Ck(4)) for some absolute constant C.