A **Kempe chain** is a concept used in the context of graph theory, specifically in the study of coloring problems and algorithms for graph coloring. Named after the mathematician J. H. Kempe, Kempe chains are useful in various applications, including the proof of the four-color theorem and in designing efficient algorithms for graph coloring. ### Definition A Kempe chain is defined as a connected sequence of vertices that alternate between two colors in a proper vertex coloring of a graph.
Articles by others on the same topic
For two colours in a proper graph colouring, a Kempe chain is a connected component of the subgraph using only those colours. Interchanging the two colours throughout one component preserves properness.