A decomposition approach to solve the selective graph coloring problem

Abstract

Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two vertices that are linked by an edge receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the aim is to pick exactly one vertex per cluster so that, among all possible selections, the number of colors needed to color the vertices in the selection is minimum. In this study, we focus on a decomposition based exact solution framework for selective coloring, and apply it rst to some special graph families, and then to general graphs with no particular structure. The special classes of graphs that we consider are perfect graphs and some special subclasses of perfect graphs, which are permutation, generalized split, and chordal graphs. In order to test the performance of our solution approach, we need graph instances from these graph classes, which led us to concentrate on the generation of random graphs from the graph classes under consideration in the second part of this study. We then test the decomposition method on graphs with di erent sizes and densities that we have produced with our generation methods, present computational results and compare them with an integer programming formulation of the problem solved by CPLEX, and a state-of-the-art algorithm from the literature. Our computational experiments indicate that our decomposition approach signi cantly improves the solution performance, especially in low-density graphs in permutation and generalized split graphs, and regardless of the edge-density in the class of chordal graphs. For perfect graphs in their general form, our approach outperforms both of the other two methods. In the case of general graphs, however, further improvements are needed to make our method competitive with the alternative methods we compare with.