A vertex-critical graph is a graph for which deleting any graph vertex lowers the chromatic
number. More specifically, a graph 
is 
-vertex-critical if its chromatic
number is 
and 
for every graph vertex 
(Jensen and Toft 1995, Chiu et al. 2024).
Every graph with chromatic number 
contains a 
-vertex-critical
vertex-induced subgraph. Also, every 
-vertex-critical graph
has minimum vertex degree at least 
, since a 
-coloring of 
could otherwise be extended to 
.
The complete graph 
is 
-vertex-critical, while the cycle
graph 
is 3-vertex-critical. Chiu et al. (2024) found exactly 17 quartic
graphs on 18 vertices that are planar graphs,
have chromatic number 4 and fractional
chromatic number 3, and are 4-vertex-critical. One of them is the Chiu
graph.
For every 
,
the shift graph 
contains exactly one 
-vertex-critical vertex-induced
subgraph. Kaiser et al. (2026, p. 2) give its vertex
set explicitly.
