Combinatorics, Probability and Computing

Table of Contents - 2003 - Volume 12, Issue 5+6  

Paper This issue contains volume twelve, parts five and six

On the Erdos–Simonovits–Sós Conjecture about the Anti-Ramsey Number of a Cycle

TAO JIANG a1 1 and DOUGLAS B. WEST a2 2

a1 Department of Mathematics and Statistics, Miami University, Oxford, OH 45056, USA (e-mail: jiangt@muohio.edu)
a2 Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: west@math.uiuc.edu)

Abstract

Given a positive integer $n$ and a family ${\cal F}$ of graphs, let $f(n,{\cal F})$ denote the maximum number of colours in an edge-colouring of $K_n$ such that no subgraph of $K_n$ belonging to ${\cal F}$ has distinct colours on its edges. Erdös, Simonovits and Sós [6] conjectured for fixed $k$ with $k\geq3$ that $f(n,C_k)\,{=}\, (\frac{k-2}{2}+\frac{1}{k-1})n + O(1)$. This has been proved for $k\leq7$. For general $k$, in this paper we improve the previous bound of $(k-2)n-\big({{k\,{-}\,1}\atop{2}}\big)$ to $f(n,C_k)\leq (\frac{k+1}{2}-\frac{2}{k-1})n - (k-2)$. For even $k$, we further improve it to $\frac{k}{2}n-(k-2)$. We also prove that $f(n,\{C_k,C_{k+1},C_{k+2}\})\leq (\frac{k-2}{2}+\frac{1}{k-1})n-1$, which is sharp.

(Received July 15 2002)
(Revised July 23 2003)


Footnotes

1 Research supported by Miami University Faculty Summer Research Grant.

2 This material is based upon work supported by the NSA under Award No. MDA904-03-1-0037, which requires the disclaimer that any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the NSA.