View Results | The Algorithm's paper | Visit Jose Antonio Martin H. page

Welcome to the Graph Coloring Web Application

A parametric-complexity exact 3-coloring solver with yes/no witnesses

by Jose Antonio Martin H.

http://www.dacya.ucm.es/jam

This site implements the algorithm described in:

http://arxiv.org/abs/1108.5405 (working paper)

The program 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 1000 vertices for planar graphs and 100 for non planar 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.

The Graph Coloring page of Jose Antonio Martin H. Powered by Google App Engine

Links of interest:

Joseph Culberson's Graph Coloring Resources Page

```
Graph Coloring on the Wikipedia
```

AMS Feature Column: Colorful Mathematics

```
Graph Coloring Problems -- The archive.
```

An empirical experiment on determining graph 3-colorability

The main idea is to test an algorithm that determines graph 3-colorability in polynomial time. Jointly this site provides some intrinsic benefits.

This is a parametric-complexity exact algorithm for solving the graph 3-(UN)COLORING problem. The algorithm has several good key-features: (i) its complexity is controlled by a parameter α,--the maximum recursion level, (ii) it generates witnesses for both Yes and No instances, i.e., a legal 3-coloring or a ``3-uncolorability witness'' (the first reported formal definition of a 3-uncolorability witness), hence the algorithm gives indubitable results, (iii) if for a given α level the algorithm is unable to produce a witness then it returns ``undetermined''; so that it can be called again with a higher α level and (iv) for α <> f(input), the algorithm scales polynomially in the size of the input graph. Furthermore, the most general version of the algorithm takes effective advantage from the possibility of self-tuning the α parameter using thus only the required computational resources for a particular problem instance.

The experiment consist of a server program that you can use to test if an input (preferably PLANAR) graph submitted trough this webpage, in a text file, is 3-colorable or not. The algorithm runs in polynomial time and returns YES/NO for an input graph instance.

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, 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,