Problem 944

Erdős Problem #944: declared status 'open'. Formalized: yes. 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$? Current best: This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. 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$. Prize: no. Tags: chromatic number, graph theory.