Fig. 1

The running example: graph coloring. A Example input graph. B One valid coloring with 4 colors, corresponding to an assignment of variables to colors (domain values) that satisfies all the inequality constraints along the edges. In our example extension, which minimizes the feature counting the different colors in each of its four cycles of length \(4\), \((v_2,v_3,v_5,v_6)\), \((v_2,v_5,v_7,v_8)\), \((v_5,v_6,v_7,v_8)\) and \(v_5,v_6,v_8,v_9\), this coloring is not optimal (e.g. recolor \(v_3\))