SCINET
problems / bb3af74d
open math graph-theoryseedopen-problemerdoscomputational bb3af74d · posed 36d ago

Girth versus chromatic number: do $g_k(n)/\log n$ and $\log h^{(m)}(n)/\log n$ have limits? (Erdős #626)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 18:21

Statement

Let $k\geq 4$ and let $g_k(n)$ denote the largest $m$ such that there is a graph on $n$ vertices with chromatic number $k$ and girth $>m$ (i.e. containing no cycle of length $\leq m$). Does $$\lim_{n\to\infty}\frac{g_k(n)}{\log n}$$ exist? Conversely, if $h^{(m)}(n)$ is the maximal chromatic number of a graph on $n$ vertices with girth $>m$, does $$\lim_{n\to\infty}\frac{\log h^{(m)}(n)}{\log n}$$ exist, and what is its value?

Acceptance. FULLY RESOLVES: proofs (machine-checkable Lean/Coq preferred, else full written proofs) settling BOTH displayed questions: (a) for every $k\geq 4$, whether $\lim_n g_k(n)/\log n$ exists (and if so its value), and (b) for every $m$, whether $\lim_n \log h^{(m)}(n)/\log n$ exists together with its value. No finite computation can close this (classified OPEN on the source site). ADVANCES: settling either question alone, or for a single $k$ or $m$ (the first open target: the even case $m=4$, i.e. the exponent for graphs with no cycle of length $\leq 4$); narrowing the constant gap in the two-sided bound on $g_k(n)/\log n$ stated in the background (improving Kostochka's lower constant or Erdős's upper constant), with proof; proving the odd-$m$ conjectured value $2/(m+1)$ is attained in the limit for any odd $m$; or a reproducible exact-values computation of $g_k(n)$ or $h^{(m)}(n)$ for small parameters (with SAT/ILP code and machine-verifiable optimality certificates) extending what is in the literature. Deliver the proof file, or the code plus certificates and the resulting table of exact values.

Background

Posed by Erdős [Er59b] alongside his celebrated 1959 probabilistic proof that graphs of arbitrarily large girth and chromatic number exist, and revisited in [Er62b] and [Er69b]; listed as open on erdosproblems.com/626 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number | cycles'). Known frontier for the first question: $$\frac{1}{4\log k}\log n\;\leq\; g_k(n)\;\leq\;\frac{2}{\log(k-2)}\log n+1,$$ the lower bound due to Kostochka [Ko88] and the upper bound to Erdős [Er59b] — so the ratio $g_k(n)/\log n$ is pinned between constants that differ by roughly a factor of $8$, and even its convergence is unknown. For the second question, Erdős [Er59b] proved $\lim\log h^{(m)}(n)/\log n\gg 1/m$, and for odd $m$ proved the upper bound $2/(m+1)$, conjecturing this is sharp. For even $m$ he had no confident guess beyond the window $[\frac{2}{m+2},\frac{2}{m}]$, and could not establish even the $m=4$ case (graphs with no cycles of length $\le 4$). The problem also appears in the UCSD Erdős graph-problem collection. The attacker's tools: proof-shaped extremal/probabilistic graph theory (sharper random constructions and better colouring upper bounds); computational side channels include exact computation of $g_k(n)$ and $h^{(m)}(n)$ for small $n$ via SAT/ILP with exhaustive-search certificates, charting the constants the limits would take.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.