Fixed-k vertex-critical edge-robustness chromatic

Open case of Erdős's problem for fixed small k · arXiv:2310.12891

arXiv Problem medium confidence— first stated 2023-10-19

Authors: Anders Martinsson, Raphael Steiner

Status partial high confidence

Skottova and Steiner (arXiv:2508.08703, August 2025) resolve the conjecture affirmatively for all k ≥ 5: for every fixed k ≥ 5 and every r ≥ 1, a k-chromatic vertex-critical graph G with χ(G − R) = k for all R ⊆ E(G), |R| ≤ r, exists; they further establish f_k(n) = Ω(n^{1/3}) for k ≥ 5. The case k = 4 remains open, coinciding with the longstanding open case of Dirac's conjecture on 4-vertex-critical graphs with no critical edge.

Cited literature (1)

partial Critical edge sets in vertex-critical graphs (2025)

Ema Skottova, Raphael Steiner · arXiv preprint · arXiv:2508.08703

Proves that for every fixed k ≥ 5 and r ≥ 1 the required k-chromatic vertex-critical graphs exist (resolving the conjecture for all k ≥ 5 via f_k(n) = Ω(n^{1/3})), while the k = 4 case remains open.

Reviewer notes. The residual open case k = 4 coincides with the longstanding open case of Dirac's 1970 conjecture (whether a 4-vertex-critical graph with no critical edge exists). arXiv:2508.08703 (Skottova–Steiner, August 2025) explicitly targets the fixed-k regime left open by the source paper and closes it for all k ≥ 5.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. For every fixed $k \geq 4$ and arbitrarily large $r$, does there exist a $k$-chromatic vertex-critical graph $G$ such that $\chi(G - R) = k$ for every $R \subseteq E(G)$ with $|R| \leq r$?

Context

Theorem 1 resolves Erdős's problem for all sufficiently large $k$ (as a function of $r$), but leaves open the regime where $k \geq 4$ is held fixed as a small constant while $r$ grows. The authors explicitly flag this as an interesting remaining open case.

Notes. Stated in prose without a labelled environment: 'Our result still leaves open Erdős' question when k ≥ 4 is fixed as a small value and r tends to infinity, and this remains an interesting open case of the problem.'

Source paper

Vertex-critical graphs far from edge-criticality
Anders Martinsson, Raphael Steiner · 2023-10-19
https://arxiv.org/abs/2310.12891 PDF source