4-chromatic edge-critical graphs with linear minimum degree: do they exist? (Erdős #1032)
Statement
We say that a graph is $4$-chromatic critical if it has chromatic number $4$ and removing any edge decreases the chromatic number to $3$. Is there, for arbitrarily large $n$, a $4$-chromatic critical graph on $n$ vertices with minimum degree $\gg n$?
Acceptance. FULLY RESOLVES: a proof that there exist $c>0$ and 4-chromatic critical graphs on arbitrarily large $n$ vertices with minimum degree $\geq cn$ — an explicit infinite family with proofs (or machine-verifiable certificates for concrete members plus a proof for the whole family) that each member has chromatic number 4, is edge-critical, and has the claimed minimum degree; OR a proof that every 4-chromatic critical graph on $n$ vertices has minimum degree $o(n)$. Machine-checkable proof preferred, else a complete written proof. ADVANCES: (a) an infinite family of 4-chromatic critical graphs with minimum degree of polynomial order strictly larger than the $n^{1/3}$ stated in the background, with proof; (b) the analogous linear-minimum-degree existence result for 5-chromatic critical graphs; (c) a nontrivial upper bound $O(n^{1-\delta})$, $\delta>0$, on the minimum degree of 4-chromatic critical graphs, with proof; (d) exact maximum minimum-degree values of 4-critical graphs for small $n$ from exhaustive enumeration, with code and an exhaustiveness certificate. Deliver the construction plus proofs/certificates, the proof file, or the enumeration code plus certified table.
Background
Erdős [Er93, p.341] wrote that he had asked this 'more than 20 years ago'; the problem also appears in [Va99, 3.60]. Listed as open on erdosproblems.com/1032 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'; page last edited 23 January 2026). Note: the site's comment tracker reports partial-result claims in the comments that are not yet incorporated into the page remarks — check the comment thread for the latest frontier. Dirac exhibited a 6-chromatic critical graph with minimum degree $>n/2$ (two disjoint odd cycles joined by all cross edges), so linear minimum degree is achievable at chromatic number 6; the question remains open for 5-chromatic critical graphs as well as the 4-chromatic case asked here. The best 4-chromatic constructions are due independently to Simonovits [Si72] and Toft [To72]: 4-chromatic critical graphs with minimum degree $\gg n^{1/3}$. Toft further conjectured that a 4-chromatic critical graph on $n$ vertices has at least $(\frac{5}{3}+o(1))n$ edges, with examples showing this would be best possible; a sharp bound of exactly this shape — every 4-critical graph on $n$ vertices has at least $(5n-2)/3$ edges — was later proved by Kostochka and Yancey (2014). Related: Erdős #917 (erdosproblems.com/917) and #944 (erdosproblems.com/944). The attacker's tool: construction search — blow-up/composition schemes aimed at beating the $n^{1/3}$ minimum-degree exponent, supported by exhaustive small-$n$ enumeration of 4-critical graphs of maximum minimum degree (checking $\chi=4$ and edge-criticality of a candidate is a finite, SAT-checkable computation).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1032 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #917 (T. F. Bloom) — related criticality problem | website |
| REF-03 | Erdős Problem #944 (T. F. Bloom) — related criticality problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.