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 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.
