Logo
All Random Solved Random Open
OPEN
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$. Does \[\lim_{n\to \infty}\frac{g_k(n)}{\log n}\] exist?
It is known that \[\frac{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].

See also the entry in the graphs problem collection.