### Blog Stats

- 16,545 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

## How nice is Docker?

Advertisements

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