The Kempe-Kittell coloring algorithm is a randomized algorithm for seeking a proper coloring of a simple graph admitting a planar graph embedding using at most four colors (Hutchinson and Wagon 1998, Wagon 2002). It extends Kempe's coloring method by making random Kempe chain color interchanges based on Kittell's (1935) operations when the original method cannot color the next vertex (Wagon 2002).
The procedure has three main steps (Wagon 2002).
1. Randomly order the vertices. Repeatedly remove a vertex of vertex degree at most five in the remaining graph, recording the removal order.
2. Restore the vertices in reverse order. Assign a color absent from the neighbors, using Kempe chain color interchanges to try to free one when all four colors appear.
3. If no color is freed, randomly choose two differently colored neighbors of the uncolored vertex. Interchange their colors throughout the Kempe chain containing one of them. Repeat until a color is freed, then resume restoration. Each interchange preserves the existing proper coloring.
Retrying Kempe's method with a new random ordering differs from making local random interchanges based on Kittell's (1935) operations (Hutchinson and Wagon 1998, Wagon 2002). Wagon (2002) did not prove termination. Stopping after a prescribed number of attempts can leave a vertex uncolored without contradicting the four-color theorem. Gethner et al. (2009) used a limit of 100 random interchanges per uncolored vertex and reported successful four-coloring in 500 runs on each of ten benchmark graphs. These tests do not establish success on every planar graph.
An exhaustive computation examined every proper coloring using four colors in which a degree-five vertex has neighbors of all four colors in all 6,274,211,344 connected planar graphs on at most 13 vertices, comprising 7,623,699,594,594 four-color-neighborhood states (E. Weisstein, Sep. 19-23, 2026). The enumeration used one representative of each unlabeled graph, tested every degree-five graph vertex and every four-color proper coloring of the graph with that graph vertex deleted (modulo global color permutation), and searched the finite graph of colorings generated by Kempe chain switches for a shortest repair. No failure was found under either transition relation tested, including the broader relation allowing both orientations of every pair of differently colored neighbors. After the standard immediate repairs were applied when possible, a shortest resolution required at most one additional Kempe chain switch. The search also resolved all 6,059,200 four-color-neighborhood states in the 36 graphs returned by GraphData["KempeCounterexample"], which have up to 50 vertices, and all 8,939 four-color-neighborhood states in the ten benchmark graphs tested by Gethner et al. (2009). The largest shortest resolution in either collection required two switches, for the Kittell graph.
The "KempeCounterexample" GraphData class is broader than the condition counted by OEIS A400130.
It records a tangle in one ordering of the faulty two-interchange argument. Such
a tangle is a counterexample to that argument even when a standard immediate repair
succeeds. At graph order 9, it also contains the Johnson skeleton graph 
, whose four-color-neighborhood states all admit a standard
immediate repair.
The numbers of connected planar graphs on 
, 2, ... vertices for which
there exist a vertex 
of vertex degree five and
a proper coloring of 
using four colors, with all four colors represented among
the neighbors of 
before any repair are 0, 0, 0, 0, 0, 25, 260, 3423, 49754,
810692, ... (OEIS A400129). The corresponding
numbers having some such state for which none of the standard immediate Kempe
chain repairs succeeds, starting with 
, are 2, 28, 670, 16994, ... (OEIS A400130),
with the initial value 2 corresponding to the Fritsch
graph and Soifer graph. In both sequences, a
graph is counted if the relevant property holds for at
least one eligible vertex and coloring,
regardless of how the vertices are labeled.
Call a graph counted by the Kempe impasse sequence vertex-primitive if none of its proper vertex-induced subgraphs is also counted. None of the 28 graphs of graph order 10 is vertex-primitive. Of these, 20 contain the Soifer graph and the other eight contain the Fritsch graph as a vertex-induced subgraph. Of the 670 graphs of graph order 11, 98 are vertex-primitive.
A successful run provides a proper coloring with at most four colors, but does not in general certify a minimum vertex coloring or the exact chromatic number.
