{"id":"palomar/PALOMAR-2026-11-19-000004","url":"https://github.com/VictorLiwentao/fc-palomar-proofs/tree/2d98cec293e789475e9cf9372472c600ecb2c64b","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-19-000004-v1.json","repo":"https://github.com/VictorLiwentao/fc-palomar-proofs","tags":["math.CO","msc:05C15","msc:05C38"],"score":0,"title":"Erdős Problem 626: Erdős's upper bound g_k(n) <= 2 log n / log(k−2) + 1","trust":"high","domain":"math.CO","source":"palomar","authors":["Wentao Li"],"reviews":0,"subject":"math.CO","summary":"For k >= 4 and all sufficiently large n, g_k(n) <= 2 log n / log(k−2) + 1, where g_k(n) is the largest m such that some graph on n vertices with chromatic number k has no cycle of length <= m. This is Erdős's upper bound (Mathematika 1962, Theorem 1) in the form his printed proof gives. Erdős's g_k(n) is the largest girth, one more than the g_k(n) used here, so the formal bound is one weaker than Theorem 1 as printed. With Erdős's lower bound of order log n, it shows that g_k(n) has order log n. Whether g_k(n)/log n converges is the open Erdős Problem 626.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-19","reactions":{},"formalized":true,"formalizes":[{"title":"On circuits and subgraphs of chromatic graphs","identifier":"doi:10.1112/S0025579300003260","relationship":"formalizes"}]}