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 (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.
|