d(1..n).

#nondomain edge(X,Y).
#external edge(X,Y).

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

color(1..k).

{color(X,C)} :- node(X), color(C), d(X).

:- not color(X,C):color(C), node(X), d(X).
:- color(X,C1), color(X,C2), color(C1;C2), C1!=C2, node(X), d(X).

:- color(X,C), color(Y,C), edge(X,Y), color(C), d(X;Y).