## Abstract

Let F(n, r, k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of K_{k}. It is shown that for every fixed k and all n > n_{0}(k), F(n, 2, k) = 2^{tk-1(n)} and F(n, 3, k) = 3^{tk-1(n)}, where t_{k-1}(n) is the maximum possible number of edges of a graph on n vertices with no K_{k} (determined by Turán's theorem). The case r = 2 settles an old conjecture of Erdos and Rothschild, which was also independently raised later by Yuster. On the other hand, for every fixed r > 3 and k > 2, the function F(n, r, k) is exponentially bigger than r^{tk-1(n)}. The proofs are based on Szemerédi's regularity lemma together with some additional tools in extremal graph theory, and provide one of the rare examples of a precise result proved by applying this lemma.

Original language | English (US) |
---|---|

Pages (from-to) | 273-288 |

Number of pages | 16 |

Journal | Journal of the London Mathematical Society |

Volume | 70 |

Issue number | 2 |

DOIs | |

State | Published - Oct 2004 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)