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

1 Answer

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.

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.

• Thanks for the nice answer! The expression you give provides a lower bound, not an upper bound, right? So, as far as you know, the best upper bound comes from Schrijver graphs? Oct 31, 2018 at 16:43
• 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