### Blog Stats

- 16,118 hits

### Last visits

- 3-edge coloring 4 4 color theorem 4ct Alfred Bray Kempe algorithm Brendan McKay Cahit spiral chains color coloring coloring maps colour cubic graphs different docker edge embedding Euler four Four color four color music four color problem four colors suffice four color theorem Francis Guthrie Fullerene graph graph coloring Graph isomorphism graphs representations Graph theory Gunnar Brinkmann Hamilton homeomorphic impasse isomorphic graphs Java Kempe Kempe chain Kenneth Appel map new features oeis pencil and paper plantri problem proof proper colorings sage sagemath tait Tait coloring theorem tutte Wolfgang Haken
### Blogroll

### Comments

### Meta

## Four color theorem: A fast algorithm – 2

https://4coloring.wordpress.com/2016/10/16/four-color-theorem-a-fast-algorithm

These are the OLD and NEW (last column) execution times on my new laptop:

- 100 – 196 vertices, 294 edges = 0 seconds – 0 seconds
- 200 – 396 vertices, 594 edges = 1 seconds – 0 seconds
- 300 – 596 vertices, 894 edges = 4 seconds – 1 second
- 400 – 796 vertices, 1194 edges = 6 seconds – 1 second
- 500 – 996 vertices, 1494 edges = 8 seconds – 2 seconds
- 600 – 1196 vertices, 1794 edges = 10 seconds – 4 seconds
- 700 – 1396 vertices, 2094 edges = 16 seconds – 6 seconds
- 800 – 1596 vertices, 2394 edges = 18 seconds – 7 seconds
- 900 – 1796 vertices, 2694 edges = 22 seconds – 9 seconds
- 1000 – 1996 vertices, 2994 edges = 26 seconds – 11 seconds

## I moved the code under github

I moved all code under github here: https://github.com/stefanutti

- I organized the folders a little betters (different github repos)
- I’m experimenting docker to deliver & deploy the Java and Python software
- I’ll also try to integrate a deep learning module, based on Tensorflow, to help me find the “missing piece”

## Four color theorem: about edges selection

For the decomposition of a graph representing a map, I’m trying to use different algorithms to select the edge to remove.

The question is:

- When you have multiple valid choices, which is the best edge to select … if any?

Some basic rules are:

- Avoid new F5 to be created
- Get rid of F5 whenever is possible, selecting the edge of a face with 2, 3 or 4 edges
- Consider to remove an edge from an F5 face only if no faces with 2, 3, 4 edges exist

Here are all possibilities. Last 2 groups (removing edges from F5 and F6) don’t have to be taken into account. I just wanted to see how it continued after the cases with faces made of 2, 3, 4 and 5 edges:

## Four color theorem: new ideas

This is what I want to try:

- Select an F2, F3 or F4 preferably when it is near an F5 and remove the edge that joins the two faces
- Analyse also the balance of the Euler’s identity when removing edges, to decide if it is better to choose other couple: F2 near the highest or other possibilities

- Let Deepmind DQN (or Tensorflow) learn the best approach for selecting faces and remove the edges
- Controls:
- The selection of the face and the edge based on the characteristics of the neighbor faces

- Scope:
- Avoid the F5 worst case (in the rebuilding phase), when it is necessary to apply the random Kempe’s color switches to solve the impasse

- Controls:

The rule: avoid F5 or at least do not create them.

- Remove F2 when near F5 –> Good (will get rid of the F5 and generate an F3)
- Remove F3 when near F5 –> Good (will get rid of the F5 and generate an F4)
- Remove F4 when near F5 –> NOT Good (will end up with another F5)
- Remove F5 when near F5 –> Good (will get rid of the F5 and generate an F6)

Other to avoid:

- Remove F2 when near F7 –> NOT Good (will end up with another F5)
- Remove F3 when near F6 –> NOT Good (will end up with another F5)
- …

NOTE:

- It is also important to check what appens to f3 and f4

## Four color theorem: what next?

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, some does not require random swithes

- Combinations
- 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 …

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

Posted in math
Tagged 4 color theorem, coloring, four color theorem, Kempe, Kenneth Appel
Leave a comment

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

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:

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