while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.
The program can be downloaded here: https://sourceforge.net/p/maps-coloring/code/ci/master/tree/ct/ct-sage/4ct.py
It requires sage to be executed:
- sage 4ct.py –help
I haven't tried many tools or library, like Mathematica, networkx or others, but the difference with the Sage implementation edge_coloring() is promising.
I have two questions:
- Is this approach to coloring planar graphs already known/used (see bolow)?
- Can you help me identifying faster known implementation for edge coloring?
The algorithm considers Tait edge coloring and the equivalency of the 3-edge-coloring (known as Tait coloring) and the 4-face-coloring (the original four color theorem for maps).
The algorithm goes like this:
- It uses a modified Kempe reduction method: it does not shrink a face (faces <= F5) down to a point, but removes a single edge from it (from faces <= F5)
- It uses a modified Kempe chain edge color switching: when restoring edges from the reduced graph, it will swap half of the colored Kempe loop
Note that while rebuilding a map, all Kempe chains are actually Kempe loops!!!
These are the stats:
- 100 – 196 vertices, 294 edges = 0 seconds
- 200 – 396 vertices, 594 edges = 1 seconds
- 300 – 596 vertices, 894 edges = 4 seconds
- 400 – 796 vertices, 1194 edges = 6 seconds
- 500 – 996 vertices, 1494 edges = 8 seconds
- 600 – 1196 vertices, 1794 edges = 10 seconds
- 700 – 1396 vertices, 2094 edges = 16 seconds
- 800 – 1596 vertices, 2394 edges = 18 seconds
- 900 – 1796 vertices, 2694 edges = 22 seconds
- 1000 – 1996 vertices, 2994 edges = 26 seconds
Almost linear … what do you think?
The first column is the original number of vertices for the planar triangulation from which the dual graph (a cubic planar graph) is computed. The seconds reported above do not consider the time to load or create the imput graph and to compute the planar embedding. You can also upload an already planar embedded graph using the -p option.
The same problem of coloring the egdes using the Sage function edge_coloring() requires very long time. I run 15 tests, and to color random graphs with 196 vertices and 294 edges, took: 7, 73, 54, 65, 216, 142, 15, 14, 21, 73, 24, 15, 32, 72, 232 seconds, for the same case where my algorithm takes less than 1 second: 100 – 196 vertices, 294 edges.
https://4coloring.wordpress.com/2016/10/16/four-color-theorem-a-fast-algorithm/
Best Answer
It sounds to me that you're not claiming that your algorithm is guaranteed to find a 4-coloring of a planar graph, just that it usually does so very quickly.
A standard reference for heuristic algorithms for coloring planar graphs is "Heuristics for Rapidly Four-Coloring Large Planar Graphs," by Craig A. Morgenstern and Henry D. Shapiro, Algorithmica 6 (1991), 869–891. They do use a modification of Kempe chain ideas, but I don't know if it's the same as yours.
You didn't specify which "implementations you found around the internet," so maybe you already know about this, but ColPack is one such package that you might try, if you haven't already. There is a paper on ColPack that describes it in detail.