Problem Statement
The anti-Ramsey number $\mathrm{AR}(n,G)$ is the maximum possible number of colours in which the edges of $K_n$ can be coloured without creating a rainbow copy of $G$ (i.e. one in which all edges have different colours).
Let $C_k$ be the cycle on $k$ vertices. Is it true that\[\mathrm{AR}(n,C_k)=\left(\frac{k-2}{2}+\frac{1}{k-1}\right)n+O(1)?\]Let $P_k$ be the path on $k$ vertices and $\ell=\lfloor\frac{k-1}{2}\rfloor$. If $n\geq k\geq 5$ then is $\mathrm{AR}(n,P_k)$ equal to\[\max\left(\binom{k-2}{2}+1, \binom{\ell-1}{2}+(\ell-1)(n-\ell+1)+\epsilon\right)\]where $\epsilon=1$ if $k$ is odd and $\epsilon=2$ otherwise?
Let $C_k$ be the cycle on $k$ vertices. Is it true that\[\mathrm{AR}(n,C_k)=\left(\frac{k-2}{2}+\frac{1}{k-1}\right)n+O(1)?\]Let $P_k$ be the path on $k$ vertices and $\ell=\lfloor\frac{k-1}{2}\rfloor$. If $n\geq k\geq 5$ then is $\mathrm{AR}(n,P_k)$ equal to\[\max\left(\binom{k-2}{2}+1, \binom{\ell-1}{2}+(\ell-1)(n-\ell+1)+\epsilon\right)\]where $\epsilon=1$ if $k$ is odd and $\epsilon=2$ otherwise?
Categories:
Graph Theory Ramsey Theory
Progress
A conjecture of Erdős, Simonovits, and Sós [ESS75], who gave a simple proof that $\mathrm{AR}(n,C_3)=n-1$. In this paper they announced proofs of the claimed formula for $\mathrm{AR}(n,P_k)$ for $n\geq \frac{5}{4}k+C$ for some large constant $C$, and also for all $n\geq k$ if $k$ is sufficiently large, but these never appeared.Simonovits and Sós [SiSo84] published a proof that the claimed formula for $\mathrm{AR}(n,P_k)$ is true for $n\geq ck^2$ for some constant $c>0$.
A proof of the formula for $\mathrm{AR}(n,P_k)$ for all $n\geq k\geq 5$ has been announced by Yuan [Yu21]
Source: erdosproblems.com/1105 | Last verified: January 19, 2026