Kempe Chain

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) regarded it as an open question whether Kempe chain exchanges can always resolve a Kempe impasse in a planar graph. They gave explicit repairs for the Kempe impasse colorings they classify on the planar map whose dual graph is the Errera graph.

For a fixed palette of colors, Kempe reachability asks whether two given proper colorings of the same graph are related by a sequence of two-color component interchanges. This question applies to general graphs, not only planar graphs. Hoang (2026) proved that it is complete for PSPACE for every fixed , even on line graphs of connected simple -regular graphs. These line graphs are connected, -regular, and claw-free.

For list colorings, a Kempe change is allowed only when every resulting vertex color belongs to that vertex's list. Wang (2026) proved that all proper list colorings are connected by such changes when the graph is 3-connected, is neither a complete graph nor the triangular prism graph, and every list has at least as many colors as the corresponding vertex degree. Wang (2026) credits ChatGPT with assistance on the maximum-degree reduction and the terminal-block recoloring argument.