Growth of girth in graphs with fixed chromatic number


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.