set colors;
set nodes;
set arcs within nodes cross nodes;
var use{c in colors} binary;
# is 1 if color c is used, 0 otherwise
var assign{i in nodes, c in colors} binary;
# is 1 if node i has color c, 0 otherwise
minimize number_of_colors: sum{c in colors} use[c];
s.t. one_color_for_each_node{i in nodes}:
sum{c in colors} assign[i,c] = 1;
s.t. different_colors_for_adjacent_nodes
{c in colors, i in nodes, j in nodes: (i,j) in arcs}:
assign[i,c] + assign[j,c] <= 1;
s.t. assign_only_chosen_colors{i in nodes, c in colors}:
assign[i,c] <= use[c];
data;
set colors:= blue red green;
set nodes:= A B C D E F;
set arcs:=
A B
B C
C D
D E
E A
C F;
