Erdős Problem a Daythe open tracker

Erdős Problem #626

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

`g k n` is \(g_k(n)\): the largest \(m\) such that some graph on \(n\) vertices has chromatic number exactly \(k\) and girth \(> m\), that is, no cycle of length \(\leq m\). The girth is `SimpleGraph.egirth`, which is `⊤` for an acyclic graph. The value `sSup ∅ = 0` for \(n < k\) affects only finitely many \(n\). For \(k \leq 2\) the set is unbounded whenever an acyclic graph on \(n\) vertices with chromatic number \(k\) exists, and then `sSup` is also \(0\); this case is not used below, where \(k \geq 4\).

`h m n` is \(h^{(m)}(n)\): the largest chromatic number of a graph on \(n\) vertices with girth \(> m\).

Let \(k \geq 4\) and let \(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. containing no cycle of length \(\leq m\)). Does \[\lim_{n\to\infty}\frac{g_k(n)}{\log n}\] exist? By `Erdos626.erdos_626.variants.kostochka` and `Erdos626.erdos_626.variants.erdos_upper`, the limit, if it exists, is a positive real number.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 7 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/626.
Prizenone
Topicsgraph theory, chromatic number, cycles
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/626
WORKING REPORT BY THIS SITE · JUL 27, 2026

Read our working report →

reduced both limits exactly to growth rates of N_k(m), proved the m=3 exponent 1/2 modulo Kim, improved liminf g_4(n)/log n to 1/(6 log 2) modulo Morgenstern, and independently verified a 66-vertex gi

PARTIAL