Tag Archives: four color theorem

Four color theorem: what next?

Posted on by
Reply

The algorithm I use to color graphs works pretty well … BUT:

  • Sometimes (very rarely) it gets into an infinite loop where also random Kempe color switches (around the entire graph) do NOT work. The good is, if I reprocess the same graph from the beginning (since in a part of the code I choose edges randomly), the algorithm usually works fine

So, what now?

I want to try other strategies while removing edges from the original graph, to avoid the above condition. I want to eliminate the need of random swithes.

The sequence I used so far is:

  • Select an F2 and if an F2 does not exist, select an F3 an so on: F4 and then F5. Once selected the face, I remove a random edge from it, only paying attention not to chose the edge if the resulting graph is 1-connected

I want to try:

  • Change the order of selecting the faces
    • Combinations
      • 2, 3, 4, 5 –> This is the default in the current version of the program (22/Nov/2016)
      • 3, 2, 4, 5
      • 4, 2, 3, 5
      • …
    • I want to try all possible combinations to see if … may be … if I’m really lucky, one does not require random swithes
  • Once selected the face, I want to try other strategies to select the edge to remove
    • random edge –> This is the default in the current version of the program (22/Nov/2016)
    • Among all the edges of the face, select the one that is shared with the face that has less edges respect to the other F
    • … that has more edges …

A planar cubic graphs to visualize what I wrote in this post:

haken-appel-hardest-case-map

Four color theorem: Infinite switches are not enough – Rectangular maps :-(

Posted on by
Reply

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:

save-graph-really-bad-case

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:

  • 1b+, 2b+, 3b+, 4b+, 5b+, 15b+, 14b-, 13b-, 5e-, 6b-, 12b-, 4e-, 8b-, 13e-, 6e-, 9b-, 12e-, 11b-, 3e-, 14e-, 10b-, 7b-, 2e-, 8e-, 9e-, 11e-, 7e-, 10e-, 15e+, 1e+

Next is the graph that shows how the graph has been converted:

really_bad_case-ariadne_step-5-12-7-32-6-15-10-ppt

Four color theorem: one switch is not enough :-(

Posted on by
Reply

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.

🙂

Four color theorem: sage and multiple edges

Posted on by
Reply

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:

kempe-half-cycle-swapping-method-sage-and-multiple-edges

Four color theorem: down to a single case!

Posted on by
Reply

This post follows directly the previous one. I’m down to a single case to prove (pag. 3).

kempe-half-cycle-swapping-method-F5-third-page-v2

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):

kempe-half-cycle-swapping-method-F5-first-page

Second page:

kempe-half-cycle-swapping-method-F5-second-page

Four color theorem: almost there?

Posted on by
1

Here there are some results that came out from the study of Kempe chains/cycles (of edges) in Tait coloring of a 3-regular planar graph.

Next is shown an image with a summary of the ideas behind this approach. I didn’t have the time to re-create this into computerized images. I will do it later. Soon will follow the F5 case for the part I’ve been experimenting with success (sub-condition where the two edges lies on two different Kempe-cycle – see below).

kempe-half-cycle-swapping-method

Here is the F4 case shown a little better:

kempe-half-cycle-swapping-method-F4

And here some deeper details of these ideas.

Theorem: In a well edge-colored (Tait coloring) 3-regular planar graph all Kempe chains are cycles

  • This can be easily proved showing that, once colored, the edges of any vertex use all the three colors (for example R, G, B), so if you are following the path of a Kempe chain, as for example an (G, B)-Kempe chain, the chain itself cannot end to a vertex, because one of the other two edges continues the kempe chain, unless that edge was exactly the first edge you started following the path of the chain … making it a Kempe cycle, as for example the (G, B)-Kempe cycle of this picture
  • Note: This theorem, in this form, is valid if the graph is already well colored (three colors). Consider that to say that the edges of a graph can be well colored (using three colors) is as difficult to prove as the four color theorem for the faces of a map. Never the less this result can be used to search a short proof of the four color theorem, even if it depends on the long proof ;-). Or (better) this result can be used without this dipendency on the long version, immerged in the reduction method when restoring the edges one at a time. As long as you solve the N+1 case (restore of F2, F3, F4, F5), starting from the map with only two faces (the island and the ocean surrounding it) the theorem is true
kempe-cycle

Picture-01: All Kempe-chains are Kempe-cycles

Steps and results toward a short proof of the 4ct:

  • Simplify the map removing one edge from one of the faces with 2, 3, 4 or 5 edges. Repeat this procedure until the map will have just one country left. This simplification procedure can be always done because the set { F2, F3, F4, F5 } represents an unavoidable set, so every 3-regular planar graphs has to have at least one face of the type included in the set
    • The procedure, for a simple map, is shown in the previous post: here
    • The idea is similar to the “patching” method used by Kempe, in which a “patch” with the same shape but a bit larger of a face (F2, F3, F4 or F5), was put over the face to shrink it down to a point. You can read the original paper here: On the Geographical Problem of the Four Colours
  • In reverse order, restore the edges that were removed, one at a time. Each time an edge is restore, we can face one of these conditions:
    • the edge restores an F2 – Note: particular and trivial case (see next point)
    • the edge restores an F3 – Note: trivial case
    • the edge restores an F4 – Note: Easy to handle
    • the edge restores an F5
  • F2 as a trivial case
    • When the restored edge reestablish an F2 face, it means the vertices of the resored edge, touch a single edge and so you have a spare color to use to solve this case (HAPPY END)
  • For all previous conditions (F2 can be seen as a particular case) there are two main possibile sub-conditions
    • CONDITION-1: The two edges touched by the restored edge are on a common Kempe cycle
      • If the two edges belong to a Kempe-cycle, the solution is easy. Apply a Kempe-chain color swapping to half (one of the two parts of the cycle being “cut” by the restored edge) of the cycle to solve this case (HAPPY END)
      • Consider that in case of the restored face is an F3, this is always the case, since the two edges touch each other. So also F3 can be regarded as a particular case
    • CONDITION-2: The two edges touched by the restored edge are NOT on a common Kempe cycle, but on distinct cycles … of course with no common edges
      • TBF: This is easy to handle for F4 and of course for F2 and F3 that are particular cases. For the F5 case I’m trying to prove that all cases can be reconducted to CONDITION-1

If this Example-02 the restored edge (in black) reestablish an F5 face. Both the edges (Green = on the left, Red = on the right) do non lie on the same (G-R)-cycle (CONDITION-2). Similar examples can be created when the two touched edges have the same color. In that case you can consider two different Kempe-chain ((R-x)-chain if the edges are colored Red) or you can easily reconduct that case to the one with different colors

kempe-cycle-F5-both-edges-not-on-cycles

Example-02: Example of restoring an F5

Now the diffucult part of the proof about the F5 case where the two edges do not lie on the same Kempe-cycle.

How can I reconduct a CONDITION-2 (edges NON on the same Kempe-cycle) to a CONDITION-1 (edges on the same Kempe-cycle)?

Four color theorem: back to the basics

Posted on by
1

Finally I bought two books about the four color theorem: “Four Colors Suffice: How the Map Problem Was Solved” by Robin Wilson e Ian Stewart; and the “The Four-Color Theorem: History, Topological Foundations, and Idea of Proof” by Rudolf Fritsch and Gerda Fritsch.

I am currently reading the first one, and I want to revisit the fundamentals by using the method Kempe employed when he believed he had solved the problem.

With these differences: I will approach it removing one edge at a time from F2, F3, F4, or F5 faces (unavoidable set) to reduce the map to two faces (including the ocean). Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. Instead of applying Kempe’s chain color switching solely to the faces, I will consider Tait coloring of the edges and apply Kempe’s chain color switching to the edges.

Follow the arrow to visualize the steps:

kempe-reduction-and-kempe's-chain-v3.png

Four color theorem: Cahit spiral chains and Tait coloring

Posted on by
Reply

I was experimenting impasses and I found this about spiral chains:

  • Consider all possible maps less than or equal to 18 faces (including the ocean)
  • Do not consider duplicates (isomophic maps)
  • There is still a very large number of possible such maps
  • Remove all maps that have faces with 2, 3, 4 edges
  • The number of maps reduces to 22 maps only
  • All these 22 maps have only one spiral chain
  • To get the Tait coloring, required me only one Kempe chain color swapping per map
  • Actually I complitely colored the spiral (the backbone) with two colors and then I finished the other edges and at the end I worked on impasses
  • Next, I’ll try the algorithm described here:

Four color theorem: 3-edge coloring, impasse and Kempe chain color swapping

Posted on by
1

It is known that for regular maps, “3-edge coloring” is equivalent to finding a proper “four coloring” of the faces of a map.

This post is about coloring impasses, fallacious Kempe chain color swapping (not solving the impasse) and an hypothesis I’d like to verify.

FIRST: What is an impasse

kempe-chain-impasse-v2

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. In the example e4 may be already colored or not, the impasse remains.

SECOND: Apply Kempe chain color swapping and problems using it

tait-and-kempe-coloring-switch-v4

One technique that can be used to solve an impasse is to apply a Kempe chain color swapping. But the problem is that this Kempe swap does not always work. This happens when the Kempe swap does not only change the color of the edge that caused the impasse (e4), but also the color of one of the other three edges involved in the impasse (e1, e2, e5 in the example).

To better understand Kempe chain color swapping, lets analyze, step by step, the labeled part the graph showed above:

  • Impasse: Since e1 and e2 are colored Green and Blue, e3 should be colored Red. But this color can’t be used because Red is already used by e4
  • To solve this impasse you can try to apply a Kempe chain coloring swapping
  • The possibilities are: (R-G)-chain and (R-B)-chain that change the color of e4
  • (R-G)-chain, involving e4 and e5 would not work, because R would end up in e5, not changing the situation … even if the continuation of the chain arrives to the vertex a
  • (R-B)-chain has a better chance to work, because would set e4 with color B, sometimes solving the impasse. I said sometimes because this is true only if the (R-B)-chain does not arrive to vertex b, swapping also the color of e2, in which case would simply mirror the problem between the vertices c and d

THIRD: Hypothesis to solve the second impasse when Kempe swap fails

Using the Java application I wrote, I started experimenting Kempe chain color swapping and found many situation where the swapping would not solve the impasse, but I also found a method, which of course needs to be proved, to solve the second impasse when Kempe chain color swapping fails (fallacious Kempe chain color swapping). If true (consider that what is written in this blog are just personal notes about an attempt) this would prove the four color theorem a very short and elegant way.

<insert video>

Hypothesis:

The hypothesis I’d like to verify is that from maps in which F2, F3, F4 faces have been previously removed (which is safe for the proof of the theorem), the fallacious Kempe chain can always be “broken” (or in different words: its path changed) along the way (using another Kempe chain coloring swap) to avoid the second impasse. After this “cut”, the original swap can be performed to solve the original impasse.

I tried this method on many maps with and without F2, F3, F4 faces, and so far it seems to work … always.

Here is an example:

impasse-kempe-chain-fallacious-v5

In this example:

  • There is an impasse between Vx and Vy. On Vx color Green could be used for the edge connecting Vx and Vy but Green is already used by e4
  • (G-R)-chain (…-e4-e3-…) swap does not work because, e4 and e3 will simply swap colors and Vy will still have a Green color starting from it
  • (G-B)-chain (e4-e5-…) swap does not work because the chain ends up to e1 (to the vertex Vx) and the impasse will remain
  • The hypotesis, that works for this example and all examples I found (maps without F2, F3, F4), is that che (G-B)-chain can be “broken” using a color swapping of the (B-R)-chain at (…-e5-e6-…), and after this swap you can apply the original (G-B)-chain color swap, that will solve the impasse. By contrary I found many example for maps containg F2, F3, F4 in which this hypotesis is not true

To be finished:

  • Insert example of maps containing F2, F3 or F4 where the second Kempe chain swap does not solve the impasse
  • Insert other examples of impasses with maps without F2, F3, F4
  • Insert video examples of impasses with maps without F2, F3, F4, that can be solved by “cutting” the fallacious chain