Status
On this page
Status
Topics
Status
On this page
Status
Topics
The anti-Ramsey number is the maximum possible number of colours in which the edges of can be coloured without creating a rainbow copy of (i.e. one in which all edges have different colours).
Let be the cycle on vertices. Is it true that
Let be the path on vertices and . If then is equal to
where if is odd and otherwise?
Source: erdosproblems.com/1105
An accepted solution exists. The statement is true.
The site's label is PROVED; the two halves rest on different evidence. Paths: the formula holds for all by Theorem 1 of Yuan (arXiv:2102.00807v3, 9 February 2021), a preprint which the site's curator accepts: the commentary, under the label PROVED, credits Yuan with an announced proof of the formula over the whole range, and the community database lists the problem as proved as of its last update, 1 February 2026; before it, Simonovits and Sós (Combinatorica 1984, refereed) proved the formula for paths on vertices and , and the 1975 announcements of proofs never appeared. Cycles: the exact value is Theorem 5 of Montellano-Ballesteros and Neumann-Lara (Graphs Combin. 21 (2005), 343--354, refereed): for every , , where is the least number of colors that forces a rainbow and with the residue of modulo , so that for all ; the displayed asymptotic is its Corollary 1 (p. 353). Before it, the 1975 and 1984 papers state the cycle formula as a conjecture (proved by its authors "only for ") and call it "still unsettled for ". The claim pages Montellano-Ballesteros and Neumann-Lara 2005 (accepted on the curator's credit and the refereed publication, partial: the cycle half), Yuan 2021 (accepted on the curator's credit, partial: the path half for all ) and Simonovits and Sós 1984 (accepted on the refereed publication, partial: long paths for large ) record the results, their postings and their acceptance evidence. The frontmatter standing derives from these pages: the problem lists its two parts, cycles and paths, and the accepted partial claims of Montellano-Ballesteros and Neumann-Lara (cycles) and Yuan (paths) settle one part each, so the derived standing is solved, proved, in agreement with the site's label, while the evidence behind each half differs as recorded here. Both halves rest on theorem statements with no proof checked, the cycle half in a refereed paper and the path half in a preprint with no refereed version.