Kempe Chains (Kc) are a useful tool for vertex coloring of a graph. NO, that's
not quite correct. Kc's come into the picture after the graph has been properly
colored.
We may have a partially or fully colored graph, but we only know the specific
coloring of a limited number of vertices. Kempe chains allow us to make state-
ments about the colors of the subgraph. Consider the simple subgraph of Figure 1.
A B A C D
1-----2-----3-----4-----5
| |
'-----------------------'
Figure 1
A KC is a path of alternately colored vertices between a pair of vertices.
A specific Kc is denoted as {(V_1,C_1):(V_2,C_2)}. For example the Vc between
v_1 & v_4 would be {(1,A);(4,C)}. Shorthand notation could be (1A,4C} or {14,AC}
If there is a Vc between two vertices, the colors of the vertices may be inter-
changed. That is, if the swap is legal. For instance v_1 and v_4 cannot swap
colors, becxause that would make both v_3 and v_4 the same color! If (1A,4C}
existed, then the color swap could not be effected.
Now consider chain {2B,4C}. If it were not for {1A,4C], the color of v_2 & v_4
could be swapped B for C & C for B. Essentially, the colors of v_2, _2 & _4
must always be three different colors!
Suppose that we have a pallette of four colors, A, B, C, & D. Then v_3 could
be D rather than A unless there is a Kc involved. Kc {3A,5D} would not work.
because this would make v_1 & v_5 the same color.
Only {1A,3A} is feasible.
Now we have three possible chains; ie, {1A,4C], {1A,3A} and {2B,4C}. But {2B,4C}
crosses both {1A,3A} and (1A,4C}. It is not unreasonable to assume that two
Kc's may intersect if and only if they have a color in common. In this case,
{2B,3C] has no common color with {1A,3A}. Therefore this configuration is not possible!
If Figure 1 has more than two chains; at least two of the chains must intersect.
The colors of Figure 1 cannot be controlled by only two chains. If a viable
configuration of three chains cannot be found; the color of one or more vertices
can be arbitrarily changed to another color!
Note that {1A,3A} is a unique chain. It has only one color and Kc's by definition
must have two colors. Fortunately, we can designate any one of the three other
colors as the alternate color!
If {1A,?,3A} is one Kc, there are six possibilites for the other two chains.
1, {1A,4C},{2B,4C]
2, {1A,4C},{2B,5D]
3, {1A,4C},{3A,5D]
4, {2B,4C},{2B,5D]
5, {2B,4C},{3A,5D]
6, {2B,5D},{3A,5D]
Let's examine each of these configurations in turn;
{1A,4C},{2B,4C]. This conf. does not involve v_5
{1A,4C},{2B,5D] {1A,4C} and {2B,5D] intersect but have no common color
{1A,4C},{3A,5D] This conf. does not involve v_2
{2B,4C},{2B,5D] This conf. is viable. [more later]
{2B,4C},{3A,5D] {2B,4C},{3A,5D] intersect but have no common color
{2B,5D},{3A,5D] This conf. does not involve v_4.
A B A C D
1-----2-----3-----4-----5
| | | | |
| |-----|-----' | Kc {2B,4C}
|-----|-----' | Kc {1A,3A}
| '-----------------| Kc {2B,5D}
'-----------------------'
Figure 2
THERE IS SOMETHING VERY WRONG HERE. FIGURE 2 CAN BE A SUBGRAPH OF A SIMPLE LOOPLESS PLANAR GRAPH. IF SO, A VERTEX CAN BE ADDED AND IF THAT VERTEX IS CONNECTED TO ALL 5 OF THE VERTICES IN FIGURE 2, THEN THE RESULTING GRAPH CANNOT BE FOUR COLORED!
Before we go any further with this thread, let's look at some
other potential 3-chain sets.
1, {1A,4C},{2B,4C},{2B,5D}
2, {1A,4C},{2B,4C},{3A,5D}
3, {1A,4C},{2B,5D},{3A,5D}
4, {2B,4C},{2B,5D},{3A,5D}
For simplicity, let's say that vertex v_1 is always colored A. Then v_4 is C
because there might be an {A,C} Kc between v_1 & v_4. The {A,C} chain is only
one of several possible chains; ie, {.
1 1 1-3 R-R
2 1-4 R-Y
3 2-4 G-Y NO
ERR ERR
2 1 1-3 R-R
2 1-4 R-Y
4 2-5 G-B NO
ERR ERR
3 1 1-3 R-R
2 1-4 R-Y
5 3-5 R-B YES
ERR ERR
4 1 1-3 R-R
3 2-4 G-Y
4 2-5 G-B NO
ERR ERR
5 1 1-3 R-R
3 2-4 G-Y
5 3-5 R-B NO
ERR ERR
6 1 1-3 R-R
4 2-5 G-B
5 3-5 R-B NO
ERR ERR
7 2 1-4 R-Y
3 2-4 G-Y
4 2-5 G-B NO
ERR ERR
8 2 1-4 R-Y
3 2-4 G-Y
5 3-5 R-B NO
ERR ERR
9 2 1-4 R-Y
4 2-5 G-B
5 3-5 R-B NO
ERR ERR
10 3 2-4 G-Y
4 2-5 G-B
5 3-5 R-B NO