Four color theorem: experimenting impasses (as in life)

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.

kempe-chain-impasse-v2

How you can solve the impasses (To be finished):

In the example: e1=red, e2=green, e3=blue, e4=red

  1. If e3 and e4 are not colored … there is no impasse → OK
  2. If e3 is the same color ex should be (blu in the example), and e4 is non colored
    1. If one of the two possible chains starting from e3: (b, r)-chain or (b, g)-chain does not end at e1 or e2
      1. Use it to change the color of e3 and solve the impasse → OK
    2. If both end at e1 or e2
      1. Try to deroute one of the two chains, using another kempe chain color swapping along the way, to fall into the previous case
        1. If the derouted original chain does non end at e1 or e2, then apply the original kempe chain color swapping and solve the impasse → OK
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses
  3. If e3 is the same color ex should be, and e4 is also colored
    1. In this case the chain (…-e3-e4-…) = (b, r)-chain would simply swap the colors of e3 and e4 and therefore will not solve the impasse, and so it is better to use the (b, g)-chain, starting from e3
      1. If this chain does not end at e2 (e1 is not a possible end because is red and the chain is blue and green, use it to change the color of e3 and solve the impasse → OK
      2. If it ends at e2
        1. Try to deroute the chain, using another kempe chain color swapping along the way, to fall into one of the previous cases
        2. If deroute does not work
          1. TBV: It seems that swapping colors around solve all type of impasses

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 though to be a counterexample, but it is not. Its signature is:

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

impasse-in-map-not-simplified

Something else to check:

  • Since once completely colored, all chains are actually loops, when it comes to the last two impasses, if you solve one impasse also the other one gets solved!
Posted in math | Tagged , , , , , | Leave a comment

Four color theorem: Cahit spiral chains and Tait coloring

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:
Posted in math | Tagged , , , | Leave a comment

Four color theorem: counterexample to the hypothesis I was verifying :-(

Bad news … to me!

This example it is a counterexample to the hypothesis I was trying to verify!

:-(

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.

hypothesis-counterexample-v2

Posted in math | Tagged , , | Leave a comment

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

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 a started experimenting Kempe chain color swapping and I found many situation where the swapping would not solve the impasse, but I also found a method, which of corse 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
Posted in math | Tagged , , , , | 1 Comment

Four color theorem: Tait edge coloring and Kempe switch

In this new version of the software you can manually color the edges of a map with three colors (RGB) and apply Kempe coloring switch on a Kempe edge chain (path or loop) (http://en.wikipedia.org/wiki/Kempe_chain).

Posted in math | Tagged , , , , | Leave a comment

Four color theorem: new video and new software

In the new version of the software, isomorphic graphs are automatically removed while processing. This way the generation of all graphs/maps is a lot faster … not as plantri but faster than before.

Download it here: sourceforge.

Using it, I generated all simplified graphs, in graphml format, up to 18 faces:

Here is the video on youtube:

Posted in math | Tagged , , | Leave a comment

Four color theorem: simplified maps and fullerenes (answer)

After having posted the question on mathoverflow, the answer arrived in a blink of an eye.

Here is the answer from Gordon Royle:

Use Gunnar Brinkmann (University of Ghent) and Brendan McKay (Australian National University)’s program “plantri” …

You will discover that there are:

  • 3 on 16 faces (as you said)
  • 4 on 17 faces
  • 12 on 18 faces
  • 23 on 19 faces
  • 73 on 20 faces

and then going to Sloane’s online encylopaedia you discover: https://oeis.org/A081621

So in short, the answer to your question is “yes, the sequence is fairly well known”.


From plantri http://cs.anu.edu.au/~bdm/plantri:

3-connected planar triangulations with minimum degree 5 (plantri -m5), and 3-connected planar graphs (convex polytopes) with minimum degree 5 (plantri -pm5).

plantri -pm5uv 12
plantri -pm5uv 13

.
nv ne nf | Number of graphs
12 30 20 | 1
13 33 22 | 0
14 36 24 | 1
15 39 26 | 1
16 42 28 | 3
17 45 30 | 4
18 48 32 | 12
19 51 34 | 23
20 54 36 | 73
21 57 38 | 192
22 60 40 | 651
23 63 42 | 2070
24 66 44 | 7290
25 69 46 | 25381
26 72 48 | 91441
27 75 50 | 329824
28 78 52 | 1204737
29 81 54 | 4412031
30 84 56 | 16248772
31 87 58 | 59995535
32 90 60 | 222231424
33 93 62 | 825028656
34 96 64 | 3069993552
35 99 66 | 11446245342
36 102 68 | 42758608761
37 105 70 | 160012226334
38 108 72 | 599822851579
39 111 74 | 2252137171764
40 114 76 | 8469193859271
Posted in math | Tagged , , , , , | Leave a comment