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

Welcome to the Graph Coloring Web Application An asymptotic-parametric-complexity exact 3-coloring solver

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

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:

YES: a legal 3-coloring is provided or
NO: a 3-uncolorability certificate, i.e., a 4-critical subgraph. is provided.

What a 3-uncolorability certificate is?

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.

External links:

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.

The experiment consist of a server program that you can use to test if an input 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 and a certificate.

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,

Лучший частный хостинг