Counting vertices of a graph with large girth and chromatic number

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.