Problem 1032

Erdős Problem #1032: declared status 'open'. Formalized: no. 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$? Current best: 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. Prize: no. Tags: chromatic number, graph theory.