In graph theory, the 3-colorability problem is a special case of graph coloring or graph labeling. It is a NP-complete problem.
The goal is as follows: Given an undirected graph G, find an assignment of colors to the nodes out of three colorss so that no adjacent nodes have the same color.
Applications of the 3-colorability problem can be found in scheduling tasks or in social networks.

- Log in to post comments

1 answer

Submitted by Thomas Linsbichler on Wed, 12/14/2011 - 10:12### Taggings:

The 3-colorablitiy problem can be solved by answer set programming (ASP), which is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems.

Given an undirected graph, for each edge from a node X to node Y you define the fact:`edge(X,Y).`

The program looks as follows:

node(X) :- edge(X,Y).

node(Y) :- edge(X,Y).

col(red,X) v col(green,X) v col(blue,X) :- node(X).

:- edge(X,Y), col(C,X), col(C,Y).

With the tool DLV (http://www.dbai.tuwien.ac.at/proj/dlv/), which was developed at the University of Calabria and the Vienna University of Technology, you can compute all stable models (answer sets) of the program and thus get a valid 3-coloring of the graph.

- Log in to post comments