Growth of girth in graphs with fixed chromatic number
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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 (k2)} +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), 170175.

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