Counting vertices of a graph with large girth and 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
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. |