Tag Archives: coloring maps

Let’s go to the beach: pentagonal regions and the Four Color Theorem

Posted on by
Reply

I need relax. Let’s go to the beach!

Personal note: I don’t know where I am headed, so don’t follow me. I am just wandering around and taking notes.

Suppose that there exist maps that are not four-colorable, perhaps only one, perhaps a few, or even infinitely many.

Now, remove from this set all maps that have regions with 2, 3, or 4 borders. For the scope of the four color theorem and without lack of generality, we can skip them. 🤞🏻 I am confident it is true, but not completely sure I can do this passage. Or at least it should be proved.

Now select a pentagonal region and regard it as the outer boundary: the ocean that surrounds all other lands.

And now walk along the shoreline.

What can we say about the five regions that face the ocean?

Can one of them be always an F5?

The answer is no, not always. Fullerene graphs show that it is possible for all F5 faces to be isolated, with no two pentagons sharing an edge. The standard example is the Buckminsterfullerene. Or, more commonly a soccer ball.

C60

Can one of them be always an F6?

Euler’s formula neither guarantees nor rules out this possibility.

1 F5 – 0 F6 – 1 F7 – 2 F8 – 3 F9 – … = 12

👉 I don’t know if there are studies done to analyze these maps. F5 always surrounded by F7 or higher.

To be continued …

  • Remove an edge between F5-F5, or F5-F6 or 😦 F5-F7+
  • Analyze all combinations of colors along the new shoreline of the reduced maps
  • And search for a contradiction to the hypothesis that there exist maps that cannot be colored with four colors

C6000 Fullerene: a playground for the Four Color Theorem coloring algorithm

Posted on by
Reply

On this great website https://networks.skewed.de/net/fullerene_structures, you can view and download fullerene structures in various formats.

Fullerenes are a perfect playground to test my four color algorithm.

I used the C6000 fullerene. 6000 atoms! A fullerene is an allotrope of carbon. Its molecules consist of carbon atoms connected by single and double bonds. A perfect 3-regular planar graphs ready to be tested.

And this is the four colored version you can play with, created using:

# python3 4ct.py -p planar_inputs/C6000.planar -c 2354 -o C6000

Actually, it is the Tait edge three colored version of the graph. This is equivalent to the four colored version of the faces.

This zip file includes the C6000.dot + C6000.edgelist files.

C6000.zipDownload

.

See you around!

Boosting performance: Sage to Python/Networkx transition

Posted on by
Reply

I converted the Sage implementation to a pure Python / Networkx solution.

  • sage 4ct.py -r 2000
  • python3 4ct_without_sage.py -r 2000
SagePython3 + Networkx
Random graph creation17 min 59 s
* RandomTriangulation		22 s
* Custom
Planar embedding16 min 09 s
* dual + set_embedding=True		0 s
* Not necessary
Elaboration2 min 12 s1 min 58 s

Here is the file:

bye_bye_sage_from_100_to_23_secs_2000_nodes.dotDownload

Other run:

  • sage 4ct.py -r 1000
  • python3 4ct_without_sage.py -r 1000
SagePython3 + Networkx
Random graph creation3 min 19 s6 s
Planar embedding2 min 44 s0 s
Elaboration14 s23 s

Optimizing Graph Coloring with Reinforcement Learning

Posted on by
Reply

This is what I will be working for a while. Restart is difficult, but necessary.

Why use Reinforcement Learning for Graph coloring?

In my Python application, that works on 3-regular planar graph, deciding which is the order of the edges to remove can be non-trivial. A naive approach randomly picks edges from F2 faces, F3, F4 or F5. This is the approach I used :-(. It leads to impasses when rebuilding the map. See https://4coloring.wordpress.com/2014/08/27/four-color-theorem-experimenting-impasses-as-in-life/

But a reinforcement learning agent can learn to make better selections over time to reduce color conflicts, I hope :-), and shed light on some properties of the graph that can be used in the proof.

The code will be here: https://github.com/stefanutti/maps-coloring-python

Remove one edge at a time from F2, F3, F4, or F5 faces. These faces represent the basic unavoidable set. This process will reduce the map to three faces, including the ocean as the external area. Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. I will consider Tait coloring of the edges and apply, when necessary, Kempe’s chain color switching to the edges.

Remove edges a then restore them

For the Agent:

  • Environment initialization = The starting uncolored 3-regular planar graphs
  • Action = Select the edge to remove from the 3-regular planar graphs
  • State = The updated 3-regular planar graphs
  • Reward = +1 if Random Kempe’s chain color switching was not necessary, -1 otherwise

Color Voronoi graphs

Posted on by
1

To color Voronoi graphs using the algorithm here https://github.com/stefanutti/maps-coloring-python, it is necessary to do some adjustments first:

  • Transform it into a 3-regular graph, by adding a frame and modifying the vertices with more than 3 edges, as shown below
  • Consider the surrounding area (out of the frame) as part of the map (the ocean) and color also that

It is known that we can also suppose that exactly three edges meet at each vertex since maps that have vertexes with more than three edges can be easily simplified without affecting the search of the coloring. In other words, if you can find a coloring for the map on the right, you can use the same coloring for the original map on the left.

Here is an example of these steps applied to the following Voronoi diagram. Three vertices have a degree greater than three.

Voronoi to 3-regular graph

Four color theorem: experimenting impasses (as in life)

Posted on by
1

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.

kempe-chain-impasse-v2

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.

  1. If e3 and e4 are not colored … there is no impasse → OK
  2. 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
  3. 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.

kempe-chain-deroute-v2

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+

impasse-in-map-not-simplified

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: work in progress

Posted on by
Reply

😦

Too many more things to do and little time:

  • Filter out duplicates. I finally found a java library to efficiently filter out all isomorphic graphs. It is a library part if the sspace project. Using it I will be able to test more complex simplified maps with lots of vertices … not risking to spend CPU time on duplicates
  • Finish the implementation of the Cahit algorithm to color the edges of a bridgeless cubic planar graph. I still need to well understand why Kempe’s chain color switching works using Cahit spiral chain method … especially when there is more than one spiral chain
  • Convert the swing application to javafx. This way I’ll be able to eliminate many third party dependencies: G, swixml, …
  • …

Bye

Four color theorem: Cahit spiral chains (step two)

Posted on by
Reply

Now the application 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 github site.

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