Crossposted from math.stackexchange.com:
Question: In this partially Tait's colored map, using only Kempe chain color swaps (as many as wanted), how many differently colored maps can I have?
This map has these Kempe chains:
- (R,G) - 1 - There is one chain in the map
- (R,B) - 2 - There are two chains in the map
- (G,B) - 1 - There is one chain in the map
Since there are two (R,B)-chains, that can be swapped independently and that affects also the other chains, I was not able to compute the number of possible combinations.
For this particular coloring, I'm trying to solve the impasse between Vx and Vy, only using swaps. After a "random" series of swaps (Kempe chain color swaps), I managed to solve the impasse, but I had to proceed randomly.
ADDED (25/Ago/2014).
Background and motivation:
- For the four color theorem I'm trying to study how "Kempe chains color swaps" apply on the edges of a "cubic graph" representing a common map, with the restriction of faces having 5 edges or more (without faces of type: F2, F3, F4). These is because I found many examples in which Kempe chain color swapping does not work for maps with faces of type F2, F3, F4, but I did not find an example of maps with only F5 or higher
Definitions:
- Tait coloring: "A 3-coloring of graph edges so that no two edges of the same color meet at a graph vertex (Ball and Coxeter 1987, pp. 265-266)" (http://mathworld.wolfram.com/TaitColoring.html)
- Kempe chain (http://en.wikipedia.org/wiki/Kempe_chain): "A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that G is a graph, with edge set E, and this time we have a colouring function. c : E -> S. If e is an edge assigned colour a, then the (a, b)-Kempe chain of G containing e is the maximal connected subset of E which contains e and whose edges are all coloured either a or b. This second definition is typically applied where S has three elements, say a, b and c, and where V is a cubic graph, that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being paths, which is simpler than in the case of the first definition."
- Properly colored: "In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color."
- Kempe chain color swap: In a partially well colored graph, the colors of a Kempe chain (a path of two alternate colors) can be swapped without problems, the resulting graph will also be properly colored
- Impasse: "Lets say you are coloring (Red, Green, Blue) the edges of a map and have properly colored a portion of it, as in the example. At a certain point you get to a vertex that has two edges already colored, for example with Red and Green (e1, e2). In this case you’d be forced to select the color Blue for the uncolored edge (ex). But it is possible that the color Blue is already used by one of the other two edges starting from vy (e3). This situation is called impasse."