Problem 944

A critical vertex, edge, or set of edges, is one whose deletion lowers the chromatic number.

Let $k\geq 4$ and $r\geq 1$ . Must there exist a graph $G$ with chromatic number $k$ such that every vertex is critical, yet every critical set of edges has size $>r$ ?

Source: erdosproblems.com/944

Graph theory
Chromatic number

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, departing from the site's label OPEN (page fetched), whose notes say that the case $k=4$ is open even for $r=1$ : the Lean proof of Kruer and Kohlmeyer, certified by Conjectures.io on 16 September 2026 and not recorded by the site at that fetch, answers the question for every $k\geq4$ and $r\geq1$ ; the standing derives from the claim page (Kruer and Kohlmeyer, 2026).

Br92: Brown, Jason I., A vertex critical graph without critical edges. Discrete Math. 102 (1992), no. 1, 99-101.
Je02: Jensen, Tommy R., Dense critical and vertex-critical graphs. Discrete Math. 258 (2002), no. 1-3, 63-84.
La02: Lattanzio, John J., A note on a conjecture of Dirac. Discrete Math. 258 (2002), no. 1-3, 323-330.
MaSt25: Martinsson, Anders and Steiner, Raphael, Vertex-critical graphs far from edge-criticality. Combin. Probab. Comput. 34 (2025), no. 1, 151-157.
SkSt25: E. Skottova and R. Steiner, Critical edge sets in vertex-critical graphs. arXiv:2508.08703 (2025).

Problem 944

Status

Proof claims

Discussion