# Problem

Determine the minimum number $$f(k,g)$$ of vertices in a graph with chromatic number at least $$k$$ and girth at least $$g$$.

In [2], an upper bound for $$f(k,g)$$ of $$k^{4g}$$ is given.

A complementary problem is to consider the maximum chromatic number $$k_g(n)$$ of graphs on $$n$$ vertices with girth $$g$$. Kostochka [2] proved that

$$\displaystyle \frac{n^{1/(g-1)}}{\log n} \leq k_g(n) \leq n^{2/(g-1)}.$$

This implies that

$$\displaystyle k^{(g-1)/2} \leq f(k,g) \leq g k^{g-1} \log k.$$

Bibliography
1 P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.
2 A. V. Kostochka, Upper bounds on the chromatic number of graphs (in Russian), Trudy Inst. Mat. (Novosibirsk) 10 (1988), 204-226.
3 P. Erdös, Problems and results in graph theory and combinatorial analysis, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), 153-163, Academic Press, New York-London, 1979.