Four color theorem: work in progress

Posted on January 8, 2013 by stefanutti

😦

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: 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”.