On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems

Research output: Contribution to journalArticle

55 Scopus citations

Abstract

For n ≧ k ≧ 3, let f(n,Ck) denote the maximum number m for which it is possible to color the edges of the complete graph Kn with m colors in such a way that each k‐cycle Ck in Kn has atleast two edges of the same color. Erdös, Simonovits, and Sós conjectured that for every fixed k ≧ 3, f(n, Ck) = n (k–2/2 + 1/k–1) + O(1), and proved it only for k = 3. It is shown that f(n, C4) = n + [1/3n] – 1, and the conjecture thus proved for k = 4. Some upper bounds are also obtained for f(n, Ck), k ≧ 5.

Original languageEnglish (US)
Pages (from-to)91-94
Number of pages4
JournalJournal of Graph Theory
Volume7
Issue number1
DOIs
StatePublished - Jan 1 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems'. Together they form a unique fingerprint.

  • Cite this