Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 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$ ?

Status. Open.

Source. erdosproblems.com/1032, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1032, https://www.erdosproblems.com/1032.

References.

[Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter IV, printed p. 341. Erdős poses the question in the words "Is there a 4-chromatic critical graph on $n$ vertices every vertex of which has degree $>\epsilon n$ (for some $\epsilon>0$ )", says he asked it more than twenty years earlier, and notes that Dirac's original example is $6$ -chromatic critical with every degree above $n/2$ . He reports the problem still open for $4$ - and $5$ -chromatic graphs, and names the independent constructions of Simonovits [36] and Toft [37] of $4$ -chromatic critical graphs on $n$ vertices with every degree greater than $cn^{1/3}$ as the best result known to him. The site cites p. 341 ([Er93,p.341]), where the library card locates the passage. Library home: erdos_1993_my_favorite_solved_unsolved_problems_graph_theory.
[Si72] Simonovits, M., On colour-critical graphs. Studia Sci. Math. Hungar. (1972), 67-81.
[To72] Toft, B., Two theorems on critical $4$ -chromatic graphs. Studia Sci. Math. Hungar. (1972), 83-89.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (10)

Graph Coloring extremal_graph_theory/erdos_1993_my_favorite_solved_unsolved_problems_graph_theory Graph Coloring Erdös: On Some Aspects of my Work with Gabriel Dirac Conjecture (p. 112): no four-chromatic edge-critical graph has all degrees linear Jensen: Dense critical and vertex-critical graphs Theorem 3 (p. 71): dense critical k-chromatic graphs of minimum degree at least d, with c_{4,4} >= 1/169 and c_{4,5} >= 9/2704 graph_coloring/simonovits_1972_colour_critical_graphs Theorem 5 (p. 68): for every even n large enough some 4-critical W^n has minimum valence at least n^{1/3}/6 Theorem 6 (p. 68): for every even n large enough some 4-critical W^n has edge-connectivity at least n^{1/3}/6

Graph