Problem Statement
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?
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?
Categories:
Graph Theory Chromatic Number Cycles
Progress
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.
Source: erdosproblems.com/626 | Last verified: January 15, 2026