A remark on the number of edge colorings of graphs

Research output: Contribution to journalArticlepeer-review


Fix a 2-coloring Hk+1 of the edges of a complete graph Kk+1. Let C(n, Hk+1) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with two colors, which contain no copy of Kk+1 colored exactly as Hk+1. It is shown that for every fixed k and all n > n0(k), if in the colored graph Hk+1 both colors were used, then C (n, Hk+1) = 2tk(n), where tk(n) is the maximum possible number of edges of a graph on n vertices containing no Kk+1. The proofs are based on Szemerédi's Regularity Lemma together with the Simonovits Stability Theorem, and provide one of the growing number of examples of a precise result proved by applying the Regularity Lemma.

Original languageEnglish (US)
Pages (from-to)565-573
Number of pages9
JournalEuropean Journal of Combinatorics
Issue number4
StatePublished - May 2006
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A remark on the number of edge colorings of graphs'. Together they form a unique fingerprint.

Cite this