Erdős 问题 #1105

问题

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?

问题陈述引自 erdosproblems.com/1105（Thomas Bloom 维护），保留英文原文。原始出处：[ESS75]。该网站上的当前状态：已证明。

AI 贡献

以下记录来自 Terence Tao 的 Wiki AI contributions to Erdős problems（数据截至 2026 年 6 月 30 日）。🟢 完整、🟡 部分、⚪ 待核实、🔴 有误。

说明

Wiki 中的分类是暂定的，也不是一份评测榜单。许多 Erdős 问题从未有过完整的文献调研，看似新的结果日后可能被发现早已存在；也有一些问题本身的表述有歧义或错误。完整的讨论见问题页面。

∎