Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 626

Statement. Let $k\geq 4$ and $g_k(n)$ denote the largest $m$ such that there is a graph on $n$ vertices with chromatic number $k$ and girth $>m$ (i.e. contains no cycle of length $\leq m$ ). Does

\lim_{n\to \infty}\frac{g_k(n)}{\log n}

exist?

Conversely, if $h^{(m)}(n)$ is the maximal chromatic number of a graph on $n$ vertices with girth $>m$ then does

\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}

exist, and what is its value?

Status. Open.

Source. erdosproblems.com/626, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #626, https://www.erdosproblems.com/626.

References.

[Er59b] Erdős, P., Graph theory and probability. Canadian J. Math. (1959), 34-38.
[Ko88] Kostochka, A. V., Upper bounds on the chromatic number of graphs. Trudy Inst. Mat. (Novosibirsk) (1988), 204-226, 265.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (13)

Graph Coloring graph_coloring/erdos_1959_graph_theory_probability Inequality (4) (p. 34): h(k,l) > l^{1+1/(2k)} for fixed k and large l, and graphs of large girth and chromatic number (p. 35)Inequality (5) (p. 35): h(2k+1,l) < c_3 l^{1+1/k} and h(2k+2,l) < c_3 l^{1+1/k}Inequality (6) (p. 37): h(k,l) > c_4 l^{1+1/(3k)} for every k and l, and r-chromatic graphs with no circuit of fewer than [c_5 log n] edges graph_coloring/exoo_2019_bounds_smallest_k_chromatic_graphs_given Lemma 1 (p. 3): the recursive lower bound n_g(k) >= n_g(k-1) + max(k, ceil(3(k-2)/2)) + 1 for g >= 4 Lemma 2 (p. 4): the Moore bound, and its consequence for n_g(k) on p. 2 Lemma 3 (p. 4): lower bounds on n_g(k) for g = 4, 5, 6, 7 from a degree-k central vertex Theorem 4 (p. 5): n_6(4) >= 26 and n_7(4) >= 30 Theorem 5 (p. 6): n_4(7) <= 77 Theorem 6 (p. 10): n_6(4) <= 66 Theorem 7 (p. 11): n_7(4) <= 171

Graph