Maximum chromatic number of triangle-free graphs: close the factor-2 gap for $f(n)$ (Erdős #1104)
Statement
Let $f(n)$ be the maximum possible chromatic number of a triangle-free graph on $n$ vertices (a graph containing no three mutually adjacent vertices). Estimate $f(n)$. The best known bounds are $$(1-o(1))\left(\frac{n}{\log n}\right)^{1/2}\leq f(n) \leq (2+o(1))\left(\frac{n}{\log n}\right)^{1/2},$$ so the task is to close the factor-2 gap between the constants — ideally determining the constant $c$ with $f(n)=(c+o(1))(n/\log n)^{1/2}$.
Acceptance. FULLY RESOLVES: a proof determining the leading-order asymptotics of $f(n)$, i.e. an explicit constant $c$ with $f(n)=(c+o(1))(n/\log n)^{1/2}$ — machine-checkable (Lean 4; a formal statement already exists in google-deepmind/formal-conjectures) preferred, else a complete written proof with all steps. ADVANCES: (a) a proof strictly improving either constant beyond the bounds stated in the background (lower constant above 1 or upper constant below 2); (b) a strict improvement to either constant in the edge version $g(m)$ beyond those stated in the background; (c) computational progress on the inverse function: a new exact value, or a strictly narrowed range, for the minimum order of a triangle-free $k$-chromatic graph beyond the A292528 values stated in the background (e.g. improving $32\leq a(6)\leq 40$), with search code and a reproducible exhaustiveness certificate. Deliver the proof file, or the search code plus certificate and the attained bounds.
Background
Posed by Erdős [Er67c]; listed as open on erdosproblems.com/1104 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). The upper bound $f(n)\leq (2+o(1))(n/\log n)^{1/2}$ is due to Davies and Illingworth [DaIl22] (the 'χ-Ramsey problem for triangle-free graphs', arXiv:2107.12288); the lower bound $(1-o(1))(n/\log n)^{1/2}$ follows from a construction of Hefty, Horn, King, and Pfender [HHKP25]. The edge version — $g(m)$, the maximum chromatic number of a triangle-free graph with $m$ edges — is known to within constants: Davies and Illingworth prove $g(m)\leq (3^{5/3}+o(1))(m/(\log m)^2)^{1/3}$, and a construction of Kim [Ki95] (from his celebrated $R(3,t)\asymp t^2/\log t$ work) gives $g(m)\gg (m/(\log m)^2)^{1/3}$. The inverse function — the minimum number of vertices in a triangle-free graph of chromatic number $k$ — is Erdős #1013 (erdosproblems.com/1013), with exact values in OEIS A292528: $1, 2, 5, 11, 22$; per that entry, $a(4)=11$ is Chvátal's minimality of the Grötzsch graph, $a(5)=22$ is due to Jensen and Royle, and Goedgebeur proved $32\leq a(6)\leq 40$. A generalisation of $f(n)$ is Erdős #920 (erdosproblems.com/920). A Lean formal statement exists in google-deepmind/formal-conjectures. The attacker's tool: on the proof side, sharpened probabilistic colouring arguments (hard-core-model/entropy methods in the Davies–Illingworth style) or improved Ramsey-type constructions; on the computational side, SAT-assisted exhaustive enumeration of small triangle-free graphs to narrow the $a(6)\in[32,40]$ window and extend OEIS A292528.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1104 (T. F. Bloom) | website |
| REF-02 | OEIS A292528 — minimal number of vertices in a triangle-free graph with chromatic number n | website |
| REF-03 | Davies–Illingworth, The χ-Ramsey problem for triangle-free graphs | arxiv |
| REF-04 | Lean formal statement (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.