Four color theorem: what next?

Posted on November 22, 2016 by stefanutti

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, one does not require random swithes
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 edges …

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

haken-appel-hardest-case-map

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:

Are these different colorings?

Posted on April 5, 2011 by stefanutti

UPDATE (18/Apr/2011)

The nunber of proper colorings (not considering permutations of colors) can be count using the “Chromatic polynomial” and dividing the result by 4! (factorial that counts the permutations). But, the chromatic polynomial is only known for few types of graphs (Triangle K3, Complete graph Kn, Petersen graph, …). I haven’t found papers on this problem. Highly propably, since the difficulty to find the Chromatic polynomial of complex graphs, there cannot be a direct formula to calculate how many different colorings exist.

I’ve posted this question here on mathoverflow.

END UPDATE

Take a look at these three graphs:

Are these really different colorings?

Before to dismiss this, do the following on the first graph:

Change Blue to Yellow (Blue was just an arbitrary color among infinite others)
Change Green to Blue
Change Yellow to Green

Now you have the second graph. Continue with this:

Change Green to Yellow
Change Red to Green
Change Yellow to Red

Now you have the third graph. Since the arbitrary nature of the choice of colors, the first graph could have been colored as the third one since the beginning.

The same result, can be obtained by changing all three colors of the first graph to three other colors. If applying the same method to the third graph, you can get the same configuration for the two graphs, it means that they can be considered, for some areas of investigation, as the same configuration.

There are more complex cases in which swapping colors won’t help to get from one coloring to the other.

In the following picture taken from http://en.wikipedia.org/wiki/Graph_coloring, the graphs named (A) and (B) are the only ones that cannot be converted into one another by swapping colors.

In particular I’m interested in regular maps, excluding all maps that can be colored with 2 or 3 colors. For what I need to analyze, maps have to be regarded as differently colored, if the same coloring cannot be obtained by subsequent exchanges of colors.

In other words, for example, once a map has been properly colored, I don’t want to count all other configurations that derive from subsequent exchanges of colors.

Since the arbitrary nature of choosing colors, these derived configurations are equivalent (for what I’m analyzing) to the first one, since they could have been obtained just choosing different colors in the first place. Instead, there are colorings that differ in such a way that exchanging colors won’t help to transform one configuration into the other.

My question is: how many “different” colorings (in the meaning I explained) exist for a given map?

I’ve only found an article on http://en.wikipedia.org/wiki/Graph_coloring that count all possible colorings including swaps.

Is there a paper that can help me on this?

Four color theorem: slow motion maps

Posted on March 21, 2011 by stefanutti

Here is a video that shows the nature of rectangular and circular maps.

All maps concerning the four color theorem (“regular maps” | “planar graphs without loops”) can be topologically transformed into rectangular and circular maps.

Four color theorem: which one is the correct graph?

Posted on March 18, 2011 by stefanutti

Wikipedia: “In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short, every planar graph is four-colorable.”

But exactly which kind of planar graphs have to be considered?:

Without loops
What about multiple edges? Why are these often excluded?

Four color theorem: potential criminal

Posted on March 12, 2011 by stefanutti

Here is the tranformation of a potential criminal map into a rectangular map. All regular maps can be topologically trasformed into rectangular or circular maps. See the theorem in T2.

Faces 5, 10, 15, 20, 25 are marked with a different color to simplify the reading of the map.

The computerized and colored version can be found here: Conversion of famous maps.

The string that represents this map and that can be used with the Java application to recreate this map is:

1b+, 2b+, 25b+, 27b+, 26b-, 24b-, 3b-, 23b-, 12b-, 22b-, 21b-, 20b-, 19b-, 15b-, 16b-, 18b-, 17b-, 11b-, 9b-, 5b-, 6b-, 8b-, 7b-, 2e-, 3e-, 4b-, 5e-, 6e-, 9e-, 10b-, 8e-, 12e-, 14b-, 13b-, 11e-, 15e-, 16e-, 14e-, 19e-, 25e-, 24e-, 23e-, 26e-, 22e-, 27e+, 21e+, 20e+, 18e+, 17e+, 13e+, 10e+, 7e+, 4e+, 1e+

Here is a picture of this map with transparency set to 15%:

Tutte’s map

Posted on March 9, 2011 by stefanutti

I corrected a mistake on Tutte’s map conversion. This one is the fixed version. Face number 25 surrounding all the other faces on the original map, is the ocean of the rectangular and circular maps.