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


  • 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."


  • $\begingroup$ Could you include in your question the definition of a "Kempe chain color swap"? While I was able to find the definition of a Kempe chain on wikipedia en.wikipedia.org/wiki/Kempe_chain I did not immediately see what you meant by a color swap, and your notation for Kempe chains was not clear to me. To keep the question self-contained, you might also include the definition of a Tait coloring. The word "impasse" is also missing a definition, but perhaps that's not important to your question. $\endgroup$ – j.c. Aug 25 '14 at 14:13
  • $\begingroup$ I suggest adding more of an introduction defining what you need, see particularly "background and motivation" of meta.mathoverflow.net/questions/882/… $\endgroup$ – j.c. Aug 25 '14 at 14:14
  • $\begingroup$ OK, thanks! I'll add some additional and more precise information later. $\endgroup$ – Mario Stefanutti Aug 25 '14 at 14:41
  • $\begingroup$ We have recently proved that counting edge colorings is #P-hard, even when restricted to your case of 3-coloring 3-regular graphs. What makes you think that counting the colorings in this particular graph would be significantly easier? $\endgroup$ – Tyson Williams Aug 26 '14 at 11:11
  • $\begingroup$ You didn't define what it means for a face to be of type F2, F3, F4, or F5. Is the following the definition? A face is of time F$n$ if it is bounded by $n$ edges. $\endgroup$ – Tyson Williams Aug 26 '14 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.