A 
-Kempe chain containing a vertex 
colored 
in a planar graph 
with a proper coloring
is the connected component containing 
in the induced
subgraph of 
on the vertices colored 
or 
(Gethner and Springer 2003, Gethner et al. 2009).
Interchanging the two colors throughout a Kempe chain preserves a proper coloring. Any edge joining the chain to a vertex outside it has an endpoint of a third color, since otherwise that vertex would belong to the same chain (Gethner et al. 2009).
The Kempe-Kittell coloring algorithm uses Kempe chain color interchanges to seek a four-coloring of a planar graph (Hutchinson and Wagon 1998, Wagon 2002). When Kempe's coloring algorithm cannot color an uncolored vertex, the repair approach tries further Kempe chain interchanges chosen from Kittell's operations to free a color and resume coloring (Gethner et al. 2009, Xie and Bowling 2026).
Gethner et al. (2009) reported successful four-coloring on all tested runs of their randomized implementation on ten benchmark graphs, including the Errera graph and Kittell graph. Their cutoff of 100 randomly selected Kempe-Kittell switches at a Kempe impasse was an implementation limit, not a mathematical bound. Experimental success does not establish guaranteed resolution of every Kempe impasse or termination with a four-coloring. Xie and Bowling (2026) described whether sequences of Kempe chain exchanges can always resolve a Kempe impasse as an open question, while giving explicit repairs for the Kempe impasse colorings of the Errera map that they classify.
