Problem 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$?
Is there, for arbitrarily large $n$, a $4$-chromatic critical graph on $n$ vertices with minimum degree $\gg n$?
Categories:
Graph Theory Chromatic Number
Progress
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].
Source: erdosproblems.com/1032 | Last verified: January 19, 2026