I realized that for some posts I may have used “Kempe loops” and “Kempe cycles” to describe closed “Kempe chains”, that in other words form closed paths (cycles). I think it would have been better always to use “Kempe cycles”.
https://en.wikipedia.org/wiki/Loop_(graph_theory)
https://en.wikipedia.org/wiki/Path_(graph_theory)
https://en.wikipedia.org/wiki/Hamiltonian_path
I generated a planar map of 10000 nodes and then colored using the 4ct python coloring program.
It did use Tait coloring (3-edge-coloring) which is equivalent to the four face coloring of the four color theorem.
It works pretty fast using:
I transformed the really bad case into a rectangular map to play with the Java program and Kempe random switches.
Here is the graph with the two edges to connect:
The two edges marked with the X, have to be joined by a new edge that form a new F5 face.
To try the Java program, rebuild this graph and play with the switches, it is possible to use this string:
Next is the graph that shows how the graph has been converted:
A new edge 12-7 that connects the edges 6-10 and 32-15.
With this case seems that infinite random switches throughout the entire graph do not solve the impasse, which is really really really bad.
Experimenting with the Python program, I have found that if you have an F5 impasse, a single switch may not be enough to solve the impasse. It means: counterexample found.
This is a bad news, since I believed that a single switch, on an appropriate edge, could have been the key to solve the theorem.
BUT
Since a limited number of switches still work, I am going to study if two switches, on appropriate edges, may work.
🙂
Implementing, using Sagemath, the algorithm of Kempe reduction and the half Kempe chain color swithing (for Tait coloring), I need to avoid multiple edges and loops … OR I’ll not be able to use functions that need embedding, as for example faces(), is_planar() and others.
Some notes:
This post follows directly the previous one. I’m down to a single case to prove (pag. 3).
I think I should move to Java coding, implementing the entire algorithm: map reduction (removing edges), color reduced map, restore of edges one at a time, adjust the coloring to the case to prove (e2 = red), apply Kc5 color switching, …, apply the half Kempe-cycle color switching.
Notes (pag. 1 and 2):
Second page:
I still think a solution may be found in Kempe chain color swapping … for maps without F2, F3 and F4 faces (or even without this restriction).
Or at least I want to try.
How you can solve the impasses (To be finished):
To explain the possible cases, without lack of generality, I can assume to start with these colors: e1=red, e2=green, e3=blue, e4=red. e4 may also be colored in green, the reasoning will not change much.
A deroute of a chain appears as in the next picture. Consider that deroutes may not work because Chain-B color swapping may change one or more of the three edges e1, e2, e4, and after appying the Chain-B swap, the chain starting with a3, may still end to one to e1, e2, e4. See this post for a real example: here.
About swaps of a partially colored map, I’ve asked a question on mathoverflow … here.
Maybe I was wrong when, in the motivation of the question (mathoverflow), I said that “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“. It seems to be possible also for maps with F2, F3, F4.
I’ll continue to search for counterexample but, for what I’ve seen so far (I tryed about 50 maps) it has been always possible to solve impasses, only proceeding by swapping colors.
This is one of the map that I thought to be a counterexample, but it is not. Its signature is:
Something else to check:
I was experimenting impasses and I found this about spiral chains:
Bad news … to me!
This example it is a counterexample to the hypothesis I was trying to verify!
Map signature: 1b+, 4b+, 6b+, 15b+, 7b-, 14b-, 8b-, 12b-, 13b-, 11b-, 9b-, 8e-, 7e-, 5b-, 6e-, 9e-, 10b-, 5e-, 4e-, 3b-, 10e-, 11e-, 12e-, 3e-, 2b-, 13e-, 14e-, 15e+, 2e+, 1e+
😦
For this example, no Kempe color switching exists along the main chain (b-r) = (1-2-3-4-5-6-7-8) that “divert” it, to make it end at a different vertex than vx. All other chains (*-g) along the main chain (b-r) involve vx or vy.
Four Color Theorem 