Four color theorem: what next?


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, some 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 …

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

haken-appel-hardest-case-map

Advertisements

About stefanutti

V: "Do you know me?" S: "yes." V: "No you don't." S: "Okay." V: "Did you see my picture in the paper?" S: "Yes." V: "No you didn't." S: "I don't even get the paper."
This entry was posted in math and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s