# Minimum number of vertices in a $k$-chromatic graph of odd girth $g$

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$$?

In this paper (also available here) 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.
On the upper bounds --- there are several different examples. One is the Schrijver subgraph of the Kneser graph (see  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
• Right,, it provides a lower bound. Both Schrijver and (generalized) Mycielski provide an upper bound which seems to be tight in the exponent of $k$ (when $k$ is large compared with $r$), due to Kierstead--Szemeredi--Trotter. For other relations of parameters, I do not remember... By the way, you may find some extra links to some results for specific series of parameters in the Intro of arxiv.org/pdf/1401.8086.pdf Oct 31, 2018 at 17:16