Tag Archives: Cahit spiral chains

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.

Four color theorem: Cahit spiral chains

Posted on by
Reply

Hi,

I’ve found some time to implement the first version of Cahit Spiral Chains algorithm.

I still need to:

  • Find all spiral chains of a given graph and not only one (changing the starting point)
  • I need to implement the concept of “nearest unused vertex to the last vertex of the last spiral chain”. This is needed to find the starting point of the next spiral <– DONE

Here is the video on youtube: