OPEN
This is open, and cannot be resolved with a finite computation.
Let $k\geq 4$ and $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. contains 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$ then does\[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\]exist, and what is its value?
It is known that\[\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].
Erdős
[Er59b] proved that\[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\gg \frac{1}{m}\]and, for odd $m$,\[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\leq \frac{2}{m+1},\]and conjectured this is sharp. He had no good guess for the value of the limit for even $m$, other that it should lie in $[\frac{2}{m+2},\frac{2}{m}]$, but could not prove this even for $m=4$.
See also
the entry in the graphs problem collection.
View the LaTeX source
Additional thanks to: David Penman
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #626, https://www.erdosproblems.com/626, accessed 2026-01-16
