The number of edge colorings with no monochromatic cliques

Noga Alon, József Balogh, Peter Keevash, Benny Sudakov

Research output: Contribution to journalArticle

37 Scopus citations

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 Kk. It is shown that for every fixed k and all n > n0(k), F(n, 2, k) = 2tk-1(n) and F(n, 3, k) = 3tk-1(n), where tk-1(n) is the maximum possible number of edges of a graph on n vertices with no Kk (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 rtk-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 languageEnglish (US)
Pages (from-to)273-288
Number of pages16
JournalJournal of the London Mathematical Society
Volume70
Issue number2
DOIs
StatePublished - Oct 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The number of edge colorings with no monochromatic cliques'. Together they form a unique fingerprint.

  • Cite this