Four color theorem: Cahit spiral chains

Posted on May 16, 2012 by stefanutti

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 (changing the starting point)
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 <– DONE

Here is the video on youtube:

Four color theorem: deep analysis of a map

Posted on March 11, 2012 by stefanutti

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

Here is the question on: 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

Posted on March 2, 2012 by stefanutti

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 coloring of the same map
Faster coloring
…

Download it from here:

https://github.com/stefanutti/maps-coloring-java

Video will be added soon on the youtube channel:

https://www.youtube.com/user/mariostefanutti/videos

Four color theorem: hello world

Posted on February 16, 2012 by stefanutti

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

Posted on December 29, 2011 by stefanutti

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

Posted on December 22, 2011 by stefanutti

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://github.com/stefanutti/maps-coloring-java/releases/download/4ct/ct-ui-swixml-2.3-jar-with-dependencies.jar

Four color theorem: videos

Posted on November 8, 2011 by stefanutti

Four videos for the four color theorem.

music	coloring algorithm
slow motion maps	java application features

Four color theorem: other representations of maps

Posted on May 19, 2011 by stefanutti

Here are some new representation of graphs:

Thanks to:

Four color theorem: representations of maps

Posted on April 25, 2011 by stefanutti

For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem.

For example, the graph-theoretic representation of maps has become so common and important that generally the four color problem is stated and analyzed directly in terms of graph theory: http://en.wikipedia.org/wiki/Four_color_theorem.

I am trying to collect other representations that may in some way help to get a different point of view on the problem. If you know one of these representations that is not listed and wish to share, report it here. If you also have a web reference that explains or shows the representation, it would be great.

The representations have to be general and applicable to all maps with the simplification that only regular maps (no exclaves or enclaves, 3 edges meeting at each vertex, etc.) can be considered.

These are some classic representations:

Natural: As a 3-regular planar graph (boundaries = edges)
Canonical: As the dual graph of the “natural” representation (region = vertex, neighbors = edges)
As a straight line drawing graph (Fáry’s theorem)
As a graph with vertices arranged on a grid
As a rectilinear cartogram

Plus, I found these:

As a circular map
As a rectangular map
As clefs (derived from rectangular maps)
As pipes map (derived from the clefs representation)
…

New representations (answers from mathoverflow):

http://en.wikipedia.org/wiki/Circle_packing_theorem (Koebe–Andreev–Thurston theorem)
As hypergraphs induced by discs (see: “ON THE CHROMATIC NUMBER OF GEOMETRIC HYPERGRAPHS” by SHAKHAR SMORODINSKY)

Here is an example of some of these representations for the original map shown:

See next post for other representations.

Counting maps

Posted on April 19, 2011 by stefanutti

I’ve posted this question on mathoverflow.

Is there a formula to count how many different topological regular maps can be created with n faces (on a sphere)?

For “regular” I intend maps in which the boundaries form a 3-regular planar graph
For “different” I intend maps that cannot be topologically transformed one into another (faces have to be considered unnamed)

I’ve been looking for a formula, but it is too difficult for me. Maybe it has a simple solution but I don’t see it.

This was my best guess, but I already know that it is not correct because full of symmetries, as it can be verified manually.

General formula:

$2\sum _{s_{(f-3)}=2f-5}^{2f-5+2} \text{...}\sum _{s_3=7}^{s_4} \sum _{s_2=5}^{s_3} \sum _{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)\left(s_3-5\right)\text{...}\left(s_{(f-3)}-((2f-5)-2)\right)$

4 faces = $2\sum _{s_1=3}^5 s_1\left(s_1-1\right)$
5 faces = $2\sum _{s_2=5}^7 \sum _{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)$

Here are the first results that can be found manually (excluding simmetrical maps):

2 faces = 0 possible regular map (an island and the ocean) (not to be counted, because not regular)
3 faces = 1 possible regular map (an island with two regions and the ocean) (two islands and the ocean wouldn’t be regular)
4 faces = 3 possible regular maps (can be verified adding a face from the previous map)
5 faces = 16 possible regular maps (with homeomorphics eliminated)
…

These are all maps up to 5 faces:

Four Color Theorem

Four Color Theorem, Guthrie, Kempe, Tait, Heawood and other people and stuff