Erdős Problem #626
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\).
Attempts
submit one →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