The *odd girth* of a graph $G$ is defined as the minimum length of an odd cycle in $G$. Let $n\_g(k)$ denote the minimum number of vertices in a $k$-chromatic graph of odd girth $g$. What are the known upper and lower bounds on $n\_g(k)$?


It is known that the order of magnitude of $n\_5(k)$ is $k^2 \log k$; this corresponds to $k$-chromatic triangle-free graphs. Is anything known for higher values of $g$?



Minimum number of vertices in a $k$-chromatic graph of odd girth $g$
In [this](https://link.springer.com/article/10.1007%2Fs10958-012-0882-4?LI=true) paper (also available [here](https://arxiv.org/abs/1201.3271)) we show that a graph having no odd cycles of length $\leq 2r-1$ and having at most
$$
 \frac{(k+r)(k+r+1)\dots(k+2r-1)}{2^{r-1}r^r}
$$
vertices is properly $k$-colorable. This provides an upper bound.


Another upper bound is provided by the paper by Kierstead, Szemeredi, and Trotter (see reference [4] in the above paper --- this also contains some upper bounds!).


On the upper bounds --- there are several different examples. One is the Schrijver subgraph of the Kneser graph (see [6] in the mentioned paper, or discussion on the first page), another one is the iterated (generalized) Mycielski construction applied to $C\_{2r+1}$; see a relate discussion in 



> 
> A. Gyarfas, T. Jensen, and M. Stiebitz, On graphs with strongly independent color-classes. // Journal of Graph Theory 46 (2004), 1–14.
> 
> 
> 


