Four color theorem: Cahit spiral chains (step two)

Now the program is able to find all spiral chains of a graph.

I still need to:

• Implement the Cahit coloring algorithm using the spiral chains
• Add some additional features to the Java application
  • Modify the settings to color the edges
  • Manual selection of the starting vertex
  • Manual coloring of the Edges
  • …

The application can be downloaded from the sourceforge site.

About the Cahit coloring algorithm there are some things that I need to undestrand before to implement the Java code.

Four color theorem: Cahit spiral chains

Hi,

I’ve found some time to implement the first version of Cahit Spiral Chains algorithm.

I still need to:

• Find all spiral chains of a given graph and not only one first one. I need to implement the concept of “nearest unused vertex to the last vertex of the last spiral chain”. This is needed to find the starting point of the next spiral chain
• Implement the Cahit coloring algorithm to find the Tait coloring of the given graph

Here is the video on youtube:

Four color theorem: deep analysis of a map

I would like to implement a brute force algorithm to search ALL the different colorings of a map.

Here is the question on: cstheory.stackexchange.com and math.stackexchange.com

In terms of graph theory I’d like to find all four colorings of the vertices of a planar graph (the dual representing the map).

I’m interested in maps in which each face is an opaque rectangle layered on all previous rectangles, overlapping partially. Each consecutive rectangle starts at a consecutive y coordinate. The next picture should better clarify what I mean.

The faces are numbered from 1 to n

• face 1 is the face on the bottom of the pile
• face (n-1) is the face at the top
• face n is the infinite face surrounding all others

For the meaning of different colorings you can refer to this question: mathoverflow.net

I was thinking to pre-set the colors of faces and use a classical brute force algorithm to get four coloring of the map. I already implemented the brute

force algorithm to find the proper coloring of a map and I can also force the color of faces to find particolar colorings.

The problem is that I’m not coming up with an algorithm to do it automatically and to be sure to find ALL colorings.

To see what I have so far, you can watch this video on youtube:

!

What I know is that:

• Since the colors of three neighbors faces can be arbitrary, face number n, face number 1 and the face touching both (face n and face 1), can have these fixed colors: blue, red, green

Manually I found these colorings:

Four color theorem: java application update

I new version of the java application is available with these new features:

• Save .png images and restore maps from the image itself (using metadata within it)
• Force coloring of faces to find different colorings of the same map
• Faster coloring
• …

Download it from here:

• https://sourceforge.net/projects/maps-coloring

Video will be added soon on the youtube channel:

• http://www.youtube.com/user/mariostefanutti/videos

Four color theorem: hello world

These translations have been taken from wikipedia, starting from http://en.wikipedia.org/wiki/Four_color_theorem. I was just curious to see if people search for the “four color theorem” only in english.

Teorema dei quattro colori
Problém čtyř barev
Firfarveproblemet
Vier-Farben-Satz
قضیه چهاررنگ
Théorème des quatre couleurs
Teorema das catro cores
משפט ארבעת הצבעים
Teorema de los cuatro colores
Dört renk teoremi
Kvarkolormapa teoremo
四色定理
ทฤษฎีบทสี่สี
Vierkleurenstelling
Négyszín-tétel
4색정리
चार रंग की प्रमेय
Problemo di quar kolori
Keturių spalvų teorema
Teorema celor patru culori
Проблема четырёх красок
…

Four color theorem: Tait edge coloring video

And here is the video that shows how to get a Tait colored map (graph) from a rectangular map.

Four color theorem: Tait edge coloring

From Wikipedia: “The four color theorem, on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one (Tait 1880). This statement is now known to be true, due to the proof of the four color theorem by Appel & Haken (1976).”

Here is a simple implementation of this equivalence, that converts a map from “4-face-colored” to “3-edge-colored”.

Here is the link to try the new functionality: https://sourceforge.net/projects/maps-coloring/