Kempe chain

Alfred B. Kempe (http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Kempe.htmlbio at St Andrews) first used these chains, now called after him, in 1879 in a “proof” of the four-color conjecture. Although Percy Heawood found a flaw in his proof 11 years later, the idea of Kempe chains itself is quite sound. Heawood used it to prove 5 colors suffice for maps on the plane, and the 1976 proof by Appel, Haken and Koch is also based on Kempe’s ideas.

The original Kempe chains were used in the context of colorings of countries on a map, or in modern terminology face colorings of a plane graph $G$ (such that no two adjacent faces receive the same color). The idea was extended by Heawood to embeddings of a graph in any other surface. Here

• a Kempe chain of colors $a$ and $b$ is a maximal connected set of faces that have either of those colors. as in: you can travel from any face in the set to any other, through the set. Maximal as in: there are no more faces of those colors you could enlarge the set with, i.e. that border the area you’ve already got.

In the modern dual formulation of the four-color theorem, faces of $G$ are replaced by vertices of the dual graph $G^{*}$ (and vice versa); vertices are adjacent (linked by an edge) in $G^{*}$ whenever the corresponding faces of $G$ were adjacent (sharing a border). It now becomes a vertex coloring problem (again, adjacent vertices must receive different colors). Here

• a Kempe chain of colors $a$ and $b$ is a maximal connected subgraph containing only vertices of those colors. Connected as usual in graph theory (there’s a path between any two vertices) and maximal as in: there are no more vertices of those colors you could enlarge the subgraph with, i.e. that are adjacent to a vertex you’ve already got.

  An alternative formulation: let $G(a,b)$ be the subgraph induced by all the vertices of color $a$ or $b$ (that is, with all the edges that run between those vertices). Now any connected component $H(a,b)$ of $G(a,b)$ is a Kempe chain.

While faces imply an embedding in a surface, the vertex version of the definition does not rely on any embedding. The chains are more useful in the context of an embedding though.

Kempe chains of edges

With edge coloring of graphs (again, with different colors for adjacent edges i.e. those that meet at a vertex), an analogous concept can defined. Here

• a Kempe chain of colors $a$ and $b$ is a maximal connected subgraph where the edges have either of those colors. Connected and maximal as before.

  An alternative formulation: let $G(a,b)$ be the subgraph consisting of all the edges of color $a$ or $b$ (with any vertices incident to them). Now any connected component $H(a,b)$ of $G(a,b)$ is a Kempe chain.

While superficially similar to the previous definition, these “Kempe chains” are rather different animals. Their structure is far simpler. At any vertex of $H(a,b)$, there can be at most one edge of color $a$ and one edge of color $b$ (at most two edges in all). Two things can happen:

• Every vertex in the chain has two such edges. In a finite graph, this must mean a closed path (cycle). Note that, being colored alternatingly, the number of edges must now be even.

• A vertex misses out on having an edge of one of those colors, and the chain stops there (it can’t miss out on both colors because then it wouldn’t be part of the chain). In a finite graph, the other end of the chain must now also terminate somewhere (at a vertex that misses out either one of the colors). The chain is an open path of one or more edges (its length can be even or odd).

Kempe chain arguments

One technique that can be used with all these types of chains is

• swapping the colors in one $H(a,b)$. This is always possible: by definition, there are no adjacent items that could lead to a color clash.

  Kempe slipped up when he swapped an $H(a,b)$ and an $H(a,c)$ without taking in account that swapping colors $a$ and $b$ in part of the graph could alter the shape and connectedness of any $H(a,c)$, but swapping colors in one Kempe chain at a time (and then taking stock of the lay of the land afresh) is quite safe.

  Swapping can be used to free up a color somewhere, see the http://planetmath.org/node/6932proof of Vizing’s theorem for a repeated use of this ploy on edge-based Kempe chains.

Specific to the use in plane graphs we have that

• if a Kempe chain forms a cycle, it disconnects the sphere or plane area into disjoint parts (on the plane, inside and outside the cycle).

Specifically when four colors are used for faces:

• The whole area is divided into red/green swathes and yellow/blue ones. Alternatively, into red/yellow and green/blue ones. Or red/blue and yellow/green ones.

Specifically for edge-based Kempe chains in regular $\rho$-valent graphs, if we try to edge-color the graph with only $\rho$ colors:

• No vertex can miss out on any of the $\rho$ colors, so every $H(a,b)$ must be a cycle (of even length).

Title	Kempe chain
Canonical name	KempeChain
Date of creation	2013-05-16 21:17:19
Last modified on	2013-05-16 21:17:19
Owner	marijke (8873)
Last modified by	unlord (1)
Numerical id	7
Author	marijke (1)
Entry type	Definition
Classification	msc 05C15
Related topic	ColoringsOfPlaneGraphs
Related topic	ProofOfVizingsTheoremForGraphs