Finding a valid 3-coloring of a graph

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

Answer Set Programming

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:
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 (, 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.