# A problem on graphs with fixed chromatic number and large girth (proposed by Erdos [1])

Let $$g_k(n)$$ denote the largest integer $$m$$ such that there is a graph on $$n$$ vertices with chromatic number $$k$$ and girth $$m$$. Is it true that for $$k \geq 4$$, $\lim_{n \rightarrow \infty} \frac{g_k(n)}{\log n}$ exists?

Erdos[1] [2] proved that for $$k \geq 4$$,

$$\displaystyle g_k(n) \leq \frac{2 \log n}{\log (k-2)} +1.$$

In the previous section, we have described the proof that

$$\displaystyle g_k(n) \geq \frac{\log n}{4 \log k}.$$

Another way to state the result of Erdos in his 1959 paper [2] is the following:

For all integers $$g \geq 4$$ and for sufficiently large $$k$$, there exists a graph $$G$$ with chromatic number at least $$k$$ and girth at least $$g$$ having at most $$k^{cg}$$ vertices, for some absolute constant $$c$$.

Bibliography
1 P. Erdös On circuits and subgraphs of chromatic graphs, Mathematika 9 (1962), 170-175.

2 P. Erdös, Graph theory and probability, Canad. J. Math. 11 (1959), 34-38.