A graph $G$ with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical.

This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Dirac's conjecture was proved, for $k=5$, by Brown [Br92]. Lattanzio [La02] proved there exist such graphs for all $k$ such that $k-1$ is not prime. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. The case $k=4$ and $r=1$ remains open.

Martinsson and Steiner [MaSt25] proved this is true for every $r\geq 1$ if $k$ is sufficiently large, depending on $r$. Skottova and Steiner [SkSt25] have improved this, proving that such graphs exist for all $k\geq 5$ and $r\geq 1$. The only remaining open case is $k=4$ (even the case $k=4$ and $r=1$ remains open).


Erdős also asked a stronger quantitative form of this question: let $f_k(n)$ denote the largest $r\geq 1$ such that there exists a $k$-vertex-critical graph on $n$ vertices such that no set of at most $r$ edges is critical. He then asks whether $f_k(n)\to \infty$ as $n\to \infty$. Skottova and Steiner [SkSt25] have proved this for $k\geq 5$, establishing the bounds\[n^{1/3}\ll_k f_k(n) \ll_k \frac{n}{(\log n)^C}\]for all $k\geq 5$, where $C>0$ is an absolute constant.

This is Problem 91 in the graph problems collection. See also [917] and [1032].

View the LaTeX source