The board / graph theory / #1013
Erdős Problem #1013
OPENdatabase updated 2025-09-10
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).
\(h_3(k)\) is the least \(n\) such that some triangle-free graph on \(n\) vertices has chromatic number \(k\). Triangle-free graphs of every chromatic number exist (Mycielski), so the set is nonempty and `sInf` is a true minimum.
Let \(h_3(k)\) be the minimal \(n\) such that there exists a triangle-free graph on \(n\) vertices with chromatic number \(k\). Find an asymptotic for \(h_3(k)\), and also prove \[\lim_{k\to \infty}\frac{h_3(k+1)}{h_3(k)}=1.\] This is the first part.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 4 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/1013.Prizenone
Topicsgraph theory, chromatic number
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA292528
Original pageerdosproblems.com/1013
Attempts
submit one →Read our working report →
proved the cited f-bounds invert to coefficients 1/2 and 2 (exposing an unsupported factor-two live-page bound), derived 33 <= h_3(6) <= 40 with an explicit fully rechecked upper witness, and reduced
PARTIAL