Is the chapter from page 869–891 of Algorithmica 6 (1991) available for free?

Yes, it usually does it very quickly. Reference for the Sage algorithm I used is here: doc.sagemath.org/html/en/reference/graphs/sage/graphs/… but there is not a reference to a paper or algorithm used. The Sage code is here: github.com/sagemath/sage/blob/master/src/sage/graphs/…. I'll try the ColPack library. thanks for the reference

Edge coloring using 3 colors, known as Tait coloring. It is equivalent to the four cilor theorem for the faces

@Tyson. What I mean is: in partially Tait colored maps with faces of type F2, F3 or F4, if I have an impasse, Kempe chain color swapping may not work to solve an impasse, no matter how many swaps I try. Instead in maps without F2, F3 and F4, in all cases (not many: 40-50 cases) that I tryed, only by swapping colors I was able to solve the impasse. But this is just an hypothesis I'm verifying and is not related to the question. It is just the motivation of the question

@Tyson. Yes, by Fn (ex: F2, F3, F4) I mean faces bounded n edges. For the question, I don't want to count colorings in general (which I know it is hard), but starting from a specific configuration (the partially colored map in the picture) AND only proceding by Kempe chain color swaps (and non adding or removing colors from the map), how many different colorings can I have. I crossposted the question here because I had not received any answer (or hint) from math.stackexchange.com.

OK, thanks! I'll add some additional and more precise information later.