Four color theorem: experimenting impasses (as in life)

Posted on August 27, 2014 by stefanutti

I still think a solution may be found in Kempe chain color swapping … for maps without F2, F3 and F4 faces (or even without this restriction).

Or at least I want to try.

How you can solve the impasses (To be finished):

To explain the possible cases, without lack of generality, I can assume to start with these colors: e1=red, e2=green, e3=blue, e4=red. e4 may also be colored in green, the reasoning will not change much.

If e3 and e4 are not colored … there is no impasse → OK
If e3 is the same color ex should be (blu in the example) and e4 is non colored
1. If one of the two possible chains starting from e3: (b, r)-chain or (b, g)-chain does not end at e1 or e2
  1. Use it to swap the color of e3 and solve the impasse → OK
2. If both end at e1 or e2
  1. Try to deroute one of the two chains, using another kempe chain color swapping along the way, to fall into one the the solvable cases (2.A)
    1. If the derouted original chain does not longer end at e1 or e2, then apply the original kempe chain color swapping and solve the impasse → OK
    2. If deroute does not work
      1. … TBV: It seems that swapping colors around solve all type of impasses
If e3 is the same color ex should be, and e4 is also colored
1. In this case the chain (…-e3–e4-…) = (b, r)-chain would simply swap the colors of e3 and e4 and therefore will not solve the impasse. It is better to use the other (b, g)-chain, starting from e3
  1. If this chain does not end at e2 (e1 is not a possible end because the chain is blue and green), use it to swap the color of e3 and solve the impasse → OK
  2. If it ends at e2
    1. Try to deroute the chain, using another kempe chain color swapping along the way, to fall into one the the solvable cases
    2. If deroute does not work
      1. … TBV: It seems that swapping colors around solve all type of impasses

A deroute of a chain appears as in the next picture. Consider that deroutes may not work because Chain-B color swapping may change one or more of the three edges e1, e2, e4, and after appying the Chain-B swap, the chain starting with a3, may still end to one to e1, e2, e4. See this post for a real example: here.

About swaps of a partially colored map, I’ve asked a question on mathoverflow … here.

Maybe I was wrong when, in the motivation of the question (mathoverflow), I said that “I found many examples in which Kempe chain color swapping does not work for maps with faces of type F2, F3, F4, but I did not find an example of maps with only F5 or higher“. It seems to be possible also for maps with F2, F3, F4.

I’ll continue to search for counterexample but, for what I’ve seen so far (I tryed about 50 maps) it has been always possible to solve impasses, only proceeding by swapping colors.

This is one of the map that I thought to be a counterexample, but it is not. Its signature is:

1b+, 9b+, 9e+, 3b+, 5b+, 7b+, 12b+, 10b-, 11b-, 5e-, 7e-, 4b-, 3e-, 2b-, 10e-, 4e-, 6b-, 11e-, 12e+, 8b+, 8e+, 6e+, 2e+, 1e+

Something else to check:

Since once completely colored, all chains are actually loops, when it comes to the last two impasses, if you solve one impasse also the other one gets solved!

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

Posted on April 18, 2011 by stefanutti

Recap (some facts about maps and coloring):

All regular maps (3-regular planar graphs) can be topologically transformed (represented) as circular or rectangular maps
In searching for a solution of the four color problem, it is possible to exclude maps with faces that have less then five neighbours
Simplified maps (no faces with less than five neighbours) of 13 faces do not exist!
The nunber of proper colorings (not considering permulations of colors) can be count using the “Chromatic polynomial” and dividing the result by 4! (factorial that counts the permutations). Chromatic polynomial is only known for few types of graphs (Triangle K3, Complete graph Kn, Petersen graph, …)
Dual graphs derived from maps can be arranged with vertices positioned on a grid (see “Rectangular grid drawings of plane graphs” by Md. Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki)
…

To implement on the Java application (https://github.com/stefanutti/maps-coloring-java):

Force faces to have fixed colors
Change swixml2 (http://code.google.com/p/swixml2) to swixml (https://github.com/swixml)
Change the graphic library G to JTS (https://www.vividsolutions.com/open-source)
…

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?

T1 was already known

Posted on April 2, 2011 by stefanutti

The theorem I proved in T1 was already known. It was found by Kempe back in 1879 in terms of graph theory (see http://en.wikipedia.org/wiki/Four_color_theorem: “Kempe also showed correctly that G can have no vertex of degree 4″). Only 132 years later … not bad.

People from http://cstheory.stackexchange.com helped me on this (to find that it was already known). See here: http://cstheory.stackexchange.com/questions/5822.

I still think my proof it is of some value, since it is not expressed in terms of graph theory (of the dual graph derived from the map).

Just another site about the four color theorem?

Posted on February 8, 2011 by stefanutti

The four color problem has already been proved by Kenneth Appel and Wolfgang Haken back in 1976 (http://en.wikipedia.org/wiki/Four_color_theorem). Since it was the first major problem that required a computer to be completed, many people are still trying to find a simple and elegant, human checkable, “pencil and paper” proof of the problem … if any.

The approach used here to solve the problem is based on two results which, I think (please, please, please verify), haven’t been considered so far.

Only maps with all faces with five or more edges can be considered when searching for a proof of the four color problem, as proved in T1 (T1 was already known by Kempe in the year 1879 – CORRECTED! 02/Apr/2011)
All regular maps, no matter the complexity, can be topologically transformed into “circular maps” or “rectangular maps”, as proved in T2

I would really like someone to verify that the approach I used so far is correct. In computer programming it is believed that is almost impossible to find errors if you are called to test your own software and this is not different for ideas. So please help!

If you like, try the application I created to generate circular and rectangular maps … and to color them automatically. The software can be found here:

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

From command line, just use the java command:

jar -jar ct-ui-swixml-VERSION-jar-with-dependencies.jar (no installation required)

Contact me for any help!

Four Color Theorem

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

Tag Archives: four color problem