Kempe Chains and Color-Swapping

Two-Color Chains in a Partial Coloring

A coloring argument often begins with a graph in which some vertices have already been colored, while others remain uncolored. The useful local object is not an arbitrary path, but a whole connected component formed using just two colors. Swapping those two colors on that component can change which colors are available at nearby uncolored vertices without creating a conflict elsewhere.

Throughout, graphs are finite and simple. A plane graph is a planar graph together with a fixed embedding in the plane, so its vertices and edges are drawn without crossings. A partial coloring with color set \(C\) is a function \(\varphi:U\to C\), where \(U\subseteq V(G)\), such that any two adjacent vertices in \(U\) receive different colors. Vertices outside \(U\) are uncolored. Properness imposes no condition on an edge with an uncolored endpoint.

In a plane graph, a Kempe chain inherits the drawing of its vertices and edges. Its component is maximal: if a colored vertex of color \(i\) or \(j\) is adjacent to a vertex in the chain, it belongs to the same chain. This maximality is essential when a swap is made.

Why Swapping Preserves Properness

Proof. Consider any edge whose two endpoints are colored after the swap. If neither endpoint is in \(K\), neither color changed, so the edge remains properly colored. If both endpoints are in \(K\), their original colors were different. Since both were in \(\{i,j\}\), they had opposite colors; interchanging \(i\) and \(j\) at both endpoints leaves them different. It remains to consider an edge with exactly one endpoint in \(K\). If the other endpoint had color \(i\) or \(j\), it would be a vertex of the \((i,j)\)-subgraph adjacent to \(K\), and hence would belong to the same connected component \(K\). Thus an endpoint outside \(K\) must have a color other than \(i,j\). The swapped endpoint still has color \(i\) or \(j\), so the edge remains proper. Edges with an uncolored endpoint impose no condition. Every edge therefore satisfies the definition of a proper partial coloring. \(\square\)

The result concerns a whole connected component, not just a convenient piece of one. Maximality ensures that an edge cannot run from the chosen chain to an outside vertex of either swapped color. A swap does not change which vertices are colored; it changes only the two color labels on \(K\).

Planar Separation Between Chains

In a plane graph, a chain can do more than permit a swap: together with two edges to a common vertex, it can form a closed curve. The Jordan curve theorem says that a simple closed curve in the plane has two complementary regions, an inside and an outside, and any continuous path between these regions must meet the curve. We use this standard topological result here; its proof is beyond this graph-theory tutorial.

Here the sectors are the two sides determined locally at \(v\) by the two incident edges. The separation statement follows by applying the Jordan curve theorem to the closed curve: near \(v\), the edges toward \(r\) and \(s\) enter opposite sides. A path from \(r\) to \(s\) must therefore cross the curve. In a plane graph, edges cannot cross, so such a path must meet a vertex or edge of the curve. In particular, a path whose vertices use colors disjoint from the colors on \(P\), and which does not use \(v\), cannot meet the curve: it cannot share a vertex with \(P\), and it cannot use either edge \(pv\) or \(vq\) without passing through \(v\).

Why This Matters in Coloring Arguments

The low-degree vertex method for coloring a planar graph begins by removing a vertex, coloring the remaining graph, and then attempting to color the removed vertex. When its neighbors have already used several colors, swapping a Kempe chain may make one of those colors available. A planar separation argument can sometimes guarantee that one of two desired swaps is possible: if one pair of alternating neighbors is connected by a chain, the corresponding closed curve blocks a connecting chain for the other pair.

This is the mechanism behind the five-color argument developed next in the course. The point here is the local logic: first identify the two-color components, then check whether a swap frees a color; if a competing chain is relevant, use the fixed embedding and cyclic order of edges to test whether planar separation forbids it. The separation argument does not say that every pair of differently colored chains is disconnected. It applies when a particular chain and two incident edges actually form a separating curve.

Common Pitfall: Swapping Only Part of a Chain

Suppose an edge \(pq\) has \(p\) red and \(q\) blue. If one swaps red and blue at \(p\) but not at \(q\), the edge becomes blue-blue, so the coloring is no longer proper. The correction is to swap the entire connected component of the red-blue subgraph containing \(p\). If \(q\) is adjacent to \(p\) and has one of the two colors, then \(q\) belongs to that same component and is swapped too. If \(q\) is outside the component, maximality guarantees that it has neither swapped color, so the edge remains proper.

A second error is to treat every Kempe chain as a simple path. A connected two-color component can branch; a simple path is selected from it only when a separation argument needs one. Also, planar separation depends on the embedding and the cyclic order at the relevant vertex. The same abstract graph with a different embedding can have different sectors and different separation conclusions.