Erdős Problem #626

declared status 'open'. Formalized: no. 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? Current best: 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\H{o}s [Er59b]. Prize: no. Tags: chromatic number, cycles, graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.