## Abstract

Fix a 2-coloring H_{k+1} of the edges of a complete graph K_{k+1}. Let C(n, H_{k+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 K_{k+1} colored exactly as H_{k+1}. It is shown that for every fixed k and all n > n_{0}(k), if in the colored graph H_{k+1} both colors were used, then C (n, H_{k+1}) = 2^{tk(n)}, where t_{k}(n) is the maximum possible number of edges of a graph on n vertices containing no K_{k+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 language | English (US) |
---|---|

Pages (from-to) | 565-573 |

Number of pages | 9 |

Journal | European Journal of Combinatorics |

Volume | 27 |

Issue number | 4 |

DOIs | |

State | Published - May 2006 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics