News: I have improved the application so that there is no time limitation. (previously 10 minutes only) |
The application accepts graphs in the DIMACS standard format specification (plain text version) such as the .col files in http://mat.gsia.cmu.edu/COLOR/instances.html (also called edge list format). A restriction of maximum 10000 vertices for planar graphs and 5000 vertices for nonplanar ones has been set (until more tests on GAE). Also a maximum value for the α-parameter is set to 5. See the historical results, solutions, proofs and a list of the graph instances in the repository (read more). Please, report any failure of the algorithm writing to me or leave a message in the comments section below. |
Let α(G) be the minimum value of α for which the algorithm is able to obtain a solution: the probability that α(G)>k decreases exponentially:
For every decision; being yes or no, a short (polynomial in the size of the input) certificate is provided:
Given a non-3-colorable input graph G; a 3-uncolorability certificate is a description of a (possibly empty) sequence of unavoidable vertex contractions, G/uv, leading to a graph containing a 4-clique subgraph; such that either:
u,v are the non-complete vertices of a diamond subgraph or,
a nested 3-uncolorability certificate for the graph G+uv, is provided. (adding a new edge uv produces a non-3-colorable graph)
So, the vertices contained in a 3-uncolorability certificate identify a 4-critical subgraph of G.
Graph Coloring Benchmarks
Network Resources for Coloring a Graph
Joseph Culberson's Graph Coloring Resources Page
Graph Coloring on the Wikipedia
AMS Feature Column: Colorful Mathematics
Graph Coloring Problems -- The archive.
After the file is uploaded the server attempts to read it as a graph and try to construct the graph data structure. If the process fails then a message is generated indicating so, and if the process succeeds then you are notified if the graph is 3-colorable and a solution is provided. The total time of computation is printed and also the α level of the graph. Also, every graph evaluation is archived in the files directory which will be an instances database of planar graphs in DIMACS format. You can also check your results just looking at the results page in order to see your graph and the result obtained for it.
In pure python planarity is tested with the planarity test of the Graph Animation ToolBox (GATO). There is an optimized version that uses the Boyer and Myrvold planarity test algorithm.
Further work will include: automated conversion from other NP-Complete problems (e.g. 3SAT) to graph 3-colorability. If you have ideas to improve the functionality of this site do not hesitate to contact me or leave a comment in this page.
Hope you find this site useful.
Bests,
© Jose Antonio Martin H.