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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-19 Formalized: true Formalizes: title=On circuits and subgraphs of chromatic graphs identifier=doi:10.1112/S0025579300003260 relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-19-000004 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.