Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be the smallest number of colours required to colour the edges of such that every contains at least 5 colours. Determine the size of .
Source: erdosproblems.com/136
An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.
Solved. Erdős and Gyárfás [EG97] proved for all and for odd , and reported (claim page (Erdős and Gyárfás, 1997)); Erdős's own report [Er97b] (item 12) prints the weaker bounds and says that he believed the upper bound closer to the truth while Gyárfás believed in the lower bound. Bennett, Cushman, Dudek and Prałat [BCDP22] proved (claim page (Bennett Cushman Dudek Pralat, 2022)), and Joos and Mubayi [JoMu22] gave a much shorter second proof of the same asymptotic (claim page (Joos and Mubayi, 2022)); both are refereed (J. Combin. Theory Ser. B 169 (2024) and Proc. Amer. Math. Soc. 152 (2024)). The site reads the instruction to determine the size of as asking for the constant in and labels the problem solved; the exact value of is not known. The site's thread holds one comment, a typographical remark of 23 July 2026.