A Kempe impasse occurs during Kempe's coloring algorithm when the next vertex to restore has five colored neighbors using all four colors and the prescribed Kempe chain interchanges do not free a color (Wagon 1999, p. 447; Gethner and Springer 2003, Gethner et al. 2009). The impasse is a property of the partial proper coloring and the vertex order, rather than of the graph alone. The Kempe-Kittell coloring algorithm attempts to resolve it using further Kempe chain interchanges based on Kittell's operations (Wagon 2002). Explicit repairs are known for the Kempe impasse colorings of the Errera planar map and specified variations (Xie and Bowling 2026).
Kempe Impasse
See also
Errera Graph, Four-Color Theorem, Kempe Chain, Kempe's Coloring Algorithm, Kempe-Kittell Coloring Algorithm, Kittell Graph, Wagon USA Map GraphExplore with Wolfram|Alpha
References
Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.Gethner, E.; Kallichanda, B.; Mentis, A. S.; Braudrick, S.; Chawla, S.; Clune, A.; Drummond, R.; Evans, P.; Roche, W.; and Takano, N. "How False Is Kempe's Proof of the Four Color Theorem? Part II." Involve 2, 249-265, 2009. https://doi.org/10.2140/involve.2009.2.249.Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, p. 447, 1999.Wagon, S. "A Machine Resolution of a Four-Color Hoax." In Proceedings of the 14th Canadian Conference on Computational Geometry (Ed. S. Wismath). Lethbridge, Alberta, Canada: University of Lethbridge, pp. 174-185, 2002. https://www.cs.uleth.ca/~wismath/cccg/proceedings/. https://i11www.iti.kit.edu/_media/teaching/winter2006/algorithmengineering/wagon00_four_color_hoax.pdf.Xie, W. and Bowling, A. "To Color the Errera Map and Its Variations Using Four Colors." J. Combin. Math. Combin. Comput. 129, 113-130, 2026. https://doi.org/10.61091/jcmcc129-09.Cite this as:
Weisstein, Eric W. "Kempe Impasse." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KempeImpasse.html