OPEN
This is open, and cannot be resolved with a finite computation.
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$?
In
[Er93] Erdős said he asked this 'more than 20 years ago'.
Dirac gave an example of a $6$-chromatic critical graph with minimum degree $>n/2$. This problem is also open for $5$-chromatic critical graphs.
Simonovits
[Si72] and Toft
[To72] independently constructed $4$-chromatic critical graphs with minimum degree $\gg n^{1/3}$. Toft conjectured that a $4$-chromatic critical graph on $n$ vertices has at least $(\frac{5}{3}+o(1))n$ vertices, and has examples to show this would be the best possible.
See also
[917] and
[944].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1032, https://www.erdosproblems.com/1032, accessed 2026-01-16
