Maximum edges of a k-chromatic critical graph: is $f_6(n)\sim n^2/4$? (Erdős #917)
Statement
Let $k\geq 4$ and let $f_k(n)$ be the largest number of edges in a graph on $n$ vertices which has chromatic number $k$ and is critical, i.e. deleting any edge reduces the chromatic number. Is it true that $$f_k(n) \gg_k n^2?$$ Is it true that $$f_6(n)\sim n^2/4?$$ More generally, is it true that, for $k\geq 6$, $$f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2?$$
Acceptance. FULLY RESOLVES: determine the asymptotics of $f_6(n)$ — prove $f_6(n)\sim n^2/4$ or disprove it by a denser construction family with proofs — and, for the general question, determine $\lim f_k(n)/n^2$ for all $k\geq 6$ with $k\equiv 0\pmod 3$ (the cases $k\not\equiv 0\pmod 3$ of the conjectured formula being already refuted, per the background, full resolution there means establishing the correct constants). Machine-checkable (Lean/Coq) proof preferred, else a complete written proof. ADVANCES: (a) for some $k\geq 6$, a construction family strictly denser than the Stiebitz lower bounds stated in the background, with proof of chromatic number, criticality, and edge count; (b) an upper bound strictly better than the Luo–Ma–Yang bound stated in the background, with proof; (c) exact values of $f_k(n)$ ($k\in\{4,5,6\}$) for small $n$ from exhaustive enumeration, with the search code and an exhaustiveness certificate. Deliver the proof file, or the construction plus verification (code checking colourability and edge-criticality of concrete members), or the enumeration code plus certified table.
Background
Posed by Erdős [Er69b] and repeated in [Er93, p.341]; listed as open on erdosproblems.com/917 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). Erdős recalled learning the definition of criticality from Dirac in 1949 and immediately asking whether $f_k(n)=o(n^2)$; to his surprise Dirac [Di52] constructed a 6-critical graph denser than $n^2/4$: joining two disjoint copies of $C_{2n+1}$ by all cross edges gives $f_6(4n+2)\geq 4n^2+8n+3$, i.e. $f_6(N)\geq N^2/4+N$ along $N\equiv 2\pmod 4$. Erdős [Er69b] generalised this: for $3\mid k$ there are infinitely many $n$ (of shape $mk/3$, $m$ odd) with $f_k(n)\geq \frac{1}{2}(1-\frac{1}{k/3})n^2+n$. STATE OF THE THREE QUESTIONS: the first is settled — Toft [To70] proved $f_k(n)\gg_k n^2$ for all $k\geq 4$. The third is disproved for $k\not\equiv 0\pmod 3$: Stiebitz [St87] constructed, for $k\geq 6$, infinitely many $n$ with $f_k(n)\geq \frac{1}{2}(1-\frac{1}{\lfloor k/3\rfloor+\delta_k})n^2$ where $\delta_k=0$ if $k\equiv 0$, $\delta_k=1/7$ if $k\equiv 1$, and $\delta_k=24/69$ if $k\equiv 2\pmod 3$, beating the conjectured constant when $k\not\equiv 0\pmod 3$. What remains open is the asymptotic for $k\equiv 0\pmod 3$ — in particular whether $f_6(n)\sim n^2/4$ — and the true growth constants generally. Upper bounds: Stiebitz proved $f_k(n)<\mathrm{ex}(n;K_{k-1})\sim\frac{1}{2}(1-\frac{1}{k-2})n^2$ for large $n$, improved by Luo, Ma, and Yang [LMY23] to $f_k(n)\leq \frac{1}{2}(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1))n^2$. Related: Erdős #944 (erdosproblems.com/944) and #1032 (erdosproblems.com/1032). The attacker's tool: exhaustive enumeration of edge-maximal $k$-critical graphs on small $n$ (canonical generation plus SAT-based chromatic/criticality checks) to compute exact values of $f_4,f_5,f_6$ and seed new constructions interpolating the Dirac/Stiebitz patterns.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #917 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #944 (T. F. Bloom) — related criticality problem | website |
| REF-03 | Erdős Problem #1032 (T. F. Bloom) — related criticality problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.