  We consider the selective graph coloring problem, which is a generalization
of the classical graph coloring problem. Given a graph together with a
partition of its vertex set into clusters, we want to choose exactly one vertex
per cluster so that the number of colors needed to color the selected set of
vertices is minimized. This problem is known to be NP-hard. In this study, we
focus on an exact cutting plane algorithm for selective graph coloring in
perfect graphs. Since there exists no suite of perfect graph instances to the
best of our knowledge, we also propose an algorithm to randomly (but not
uniformly) generate perfect graphs, and provide a large collection of instances
available online. We conduct computational experiments to test our method on
graphs with varying size and densities, and compare our results with a
state-of-the-art algorithm from the literature and with solving an integer
programming formulation of the problem by CPLEX. Our experiments demonstrate
that our solution strategy significantly improves the solvability of the
problem.
