Welcome to the Graph Coloring Web Application

The Graph Coloring Web Application

An Asymptotic Parametric Complexity (Exact) 3-Coloring Solver

 Please, upload your (DIMACS edge-list) graph file:
Set the max α parameter:    (for planar graphs it is just ignored and fixed to 1)
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.
 
 
Powered by Google App Engine
comments powered by Disqus

About the algorithm

 

Asymptotic properties:

Let α(G) be the minimum value of α for which the algorithm is able to obtain a solution: the probability that α(G)>k decreases exponentially:

 

Verifiability of the results:

For every decision; being yes or no, a short (polynomial in the size of the input) certificate is provided:

What is a 3-uncolorability certificate?

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:

  1. u,v are the non-complete vertices of a diamond subgraph or,

  2. 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.

External links:

An empirical experiment on determining graph 3-colorability

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.

 

eXTReMe Tracker