Champe’s change / champe change swaps, fanning in graph theory

graph theory

I'm revisiting graph theory from my own old notes and these terms are mentioned near discussion of graph coloring. More specifically, near vizing's theorem which is

$$ \Delta(G) + 1 \text{ is a sufficient number of colors for edge-coloring } G$$

I believe that I must have misheard or misspelled these terms. Simple google searches don't reveal anything either. I've noted "search extra: champe's change, champe's change swaps and fanning" so there's no context available from the sentence.

However, the following note about swapping colors in proper colorings might give more clues which I made just before this line:

For two color classes (set of vertices associated with every color), you don't need to swap entire color classes to maintain a proper coloring, but you may also swap within components induced by the two color classes.

e.g.

// initial coloring      // swapped 1 and 2 within one component induced 
                         // by them. Note we didn't have to touch the two 
                         // disconnected vertices on the right 
1  2   2                 2  1     2
 \/ \ /                   \/      
 /\ /3\       -------->   /\
1  2   2                 2  1     2

Best Answer

You're thinking of Kempe chains, which are a tool used in:

  • some proofs of the five-color theorem for planar graphs;
  • Kempe's original (wrong) proof of the four-color theorem for planar graphs;
  • Maybe a few other settings as well.

Let me try to explain the idea in the context of the five-color theorem. Here, we're trying to prove that all $n$-vertex planar graphs can be vertex-colored with at most $5$ colors, by induction on $n$.

We can show that in any planar graph, there is a vertex of degree at most $5$. If we're trying to $5$-color an $n$-vertex graph $G$, we can find a vertex $v$ with $\deg(v) \le 5$, and color $G-v$ first (by the induction hypothesis). We can extend this coloring to a coloring of $G$, by giving $v$ a color not used by its neighbors, unless $v$'s neighbors use all $5$ colors between them.

If $v$ has $5$ neighbors of $5$ different colors, we need to change the coloring of $G-v$ before we can complete it to a coloring of $G$. This is what Kempe chains are good for.

Suppose that two of the colors are red and yellow. We want to recolor $G-v$ so that $v$ does not have any red neighbors. To do that,

  1. We take $v$'s existing red neighbor $w$, and color it yellow.
  2. This may cause other conflicts, if $w$ had yellow neighbors; fix them by recoloring those neighbors red.
  3. If $w$'s formerly-yellow neighbors had red neighbors of their own, those need to be recolored yellow, and so on.

We can keep going this way, no problem. The (red,yellow) Kempe chain containing $w$ is the set of all vertices we end up recoloring this way: swapping red to yellow and vice versa.

Once we're done, we may or may not have fixed the problem of $v$ having red neighbors. Certainly, $w$ is no longer red: it's yellow now. But what if the Kempe chain we found contains $v$'s yellow neighbor? Then that yellow neighbor becomes red; $v$ still has neighbors of all five colors.

In this case, we are saved by arguing that not all Kempe chains can loop around in this way. For example, if the colors around $v$ go red, blue, yellow, green, purple in that order, then the (red, yellow) chain and the (blue, green) chain can't both loop around, because then the chains would end up crossing.

In other applications, we make different arguments.

Related Question