The selective graph coloring problem

Abstract

In the classical graph coloring problem, the vertices of a given graph are colored such that no two adjacent vertices take the same color with the objective of coloring the whole graph with the minimum number of colors. The minimum number of colors that is needed to color a graph is called the chromatic number of the graph. It is known that the decision version of the problem is NP-complete and the optimization version of the problem is NP-hard. The selective graph coloring problem is a generalization of the classical graph coloring problem, where a graph and a partition of its vertices into di erent clusters are given as an input and the objective is assigning one color to one vertex in each cluster so that two adjacent vertices get di erent colors and the total number of colors is minimized. The selective graph coloring problem helps modeling and solving several real life problems. Rebuilding or repairing a cellular phone network after a disaster and allocating new frequencies to these transmitters and scheduling problems with selection among a xed set of time windows for each task are examples of real life problems for which the selective graph coloring problem will be helpful. Such various applications and the intractable nature of the selective graph coloring problems made the usage of heuristic methods inevitable. The main subject of this thesis is developing new heuristic approaches and exact methods for the solution of the selective graph coloring problem. For this purpose, several heuristic approaches and exact methods have been tried on some graph classes and their e ciency is compared through experiments.