Kempe's coloring algorithm is a procedure for attempting to color a simple graph admitting a planar graph embedding with at most four colors using Kempe chain color interchanges. It comes from Kempe's (1879) flawed proof of the four-color theorem.
Repeatedly remove a vertex of vertex degree at most five from the remaining graph, recording the removal order. Restore the vertices in reverse order, assigning each a color absent from its neighbors. If all four colors appear, try to free one by interchanging the two colors throughout a suitable Kempe chain (Kempe 1879, Wagon 2002). Such a vertex always exists because every planar graph has average vertex degree less than six. Vertices of larger degree may remain, but the removal step never needs to select one.
For four neighbors, their cyclic order in a planar graph embedding guarantees that a suitable interchange frees a color. For five neighbors displaying all four colors, one color is repeated. Kempe's (1879) argument tries interchanges to remove a color appearing once, then two interchanges to remove the repeated color. The latter step is flawed because the first interchange can change the chains needed for the second. Gethner et al. (2009) showed that one order of these two interchanges can succeed when the other fails. The Errera graph provides an explicit example in which the remaining vertex cannot be colored by this procedure (Wagon 2002).
Failure of a particular removal order does not imply that the graph needs five colors. A partial proper coloring that obstructs the argument is not by itself a counterexample to the algorithm. The obstruction must arise during the coloring procedure. The Kempe-Kittell coloring algorithm adds local random Kempe chain interchanges to try to resolve such failures (Wagon 2002).
The following graphs contain induced subgraphs admitting partial proper colorings
using four colors in which the faulty two-interchange argument tangles the Kempe
chains. Here 
is the vertex count of the
full graph, not necessarily of the smaller induced
subgraph witnessing the failure. The table lists named examples and members of
standard families, not every cataloged example. For the Johnson
skeleton graphs, the subscript is the Johnson solid
index. The smaller historical examples are illustrated above. A tangle for one interchange
order need not persist for the reverse order (Gethner et al. 2009).
 | graph name |
| 9 | Fritsch graph |
| 9 | Johnson
skeleton graph  |
| 9 | Soifer graph |
| 10 | Johnson skeleton graph  |
| 15 | Poussin graph |
| 16 | Johnson
skeleton graph  |
| 16 | Johnson skeleton graph  |
| 17 | Errera graph |
| 23 | Kittell graph |
| 24 | Dirac four-color map graph |
| 24 | Snub cubical graph |
| 25 | Heawood four-color map graph |
| 25 | Saaty four-color map graph |
| 25 | Soifer four-color map graph |
| 42 | pentakis icosidodecahedral graph |
| 50 | Wagon USA map graph |
Several of these examples are triangulated graphs, admitting a planar graph embedding in which
every graph face is bounded by three edges.
These include the Johnson skeleton graph 
and the pentakis icosidodecahedral
graph. The coloring argument depends on vertex
adjacency and the planar graph embedding,
not on a geometric realization by equilateral
triangles.
Some examples (though not the Soifer graph) also correspond to the skeletons of (possibly degenerate)
deltahedra (E. Weisstein, Mar. 7, 2022).
In particular, the Fritsch graph is the skeleton
of the triaugmented triangular prism.
The Johnson skeleton graph 
is likewise the skeleton
of a deltahedron, the gyroelongated
square dipyramid. The Errera graph is the skeleton of two pentagon-adjoined gyroelongated
pentagonal pyramids.
