Graph 3-Coloring with ASP

3col.lp

% Instance format:
% v/1 for vertices.
% e/2 for edges.

% Example:
% v(1..4).
% e(1,2).
% e(1,3).
% e(3,4).

% Two connected vertices must not have the same color.
:- e(V,U), c(V,C), c(U,C).

% One vertex must not have two different colors.
:- c(V,C1), c(V,C2), C1 != C2.

% Choose one color per vertex.
c(V,1) :- not c(V,2), not c(V,3), v(V).
c(V,2) :- not c(V,1), not c(V,3), v(V).
c(V,3) :- not c(V,1), not c(V,2), v(V).

% Disjunctive flavour:
% c(V,1) v c(V,2) v c(V,3) :- v(V).

% Auxiliary read-off.
red(V) :- c(V,1).
green(V) :- c(V,2).
blue(V) :- c(V,3).

% Example invocaton:
% dlv -silent -filter=red,green,blue 3col.lp