set V; # nodes
param q default card(V); # number of colors to try
# we definitely won't need more colors than there are vertices
set C = 1..q; # set of potential colors
set E within V cross V; # edges
var x {V cross C} binary;
# x[v,c] = 1 if vertex v is colored using color c, and x[v,c] = 0 otherwise
var y {C};
# encodes whether color c is used (1 = used)
# x binary => y binary, so we don't need to declare that here
# objective function: minimize the number of colors used
minimize NumOfUsedCols:
sum {c in C} y[c];
# each vertex has exactly one color
s.t. AssignColor {v in V}:
sum {c in C} x[v,c] = 1;
# adjacent vertices must not have the same color
s.t. Conflict {(v,w) in E, c in C}:
x[v,c] + x[w,c] <= 1;
# if vertex v has color c, then color c is used
s.t. SetIndicator {v in V, c in C}:
x[v,c] <= y[c];
# we allow that y[c] = 1 although c is not used.
# However, this will never occur in an optimal solution, so we
# don't have to exclude it explicitly