Chromatic scheduling

A classical problem in combinatorics and combinatorial optimization is the graph coloring problem, which asks for the smallest number of colors required to color the vertices of a graph so that adjacent vertices receive distinct colors. Graph coloring arises in several applications of scheduling and resource allocation. However, problems arising in these applications are more general than classical coloring. In this thesis, we present several approximation algorithms and complexity results for such generalized coloring problems.

In this thesis, we deal with the class of perfect graphs and sub-classes of perfect graphs on which the classical coloring problem can be solved in polynomial time. However, the coloring problems we consider are NP-hard even on very restricted sub-classes of perfect graphs. The contributions of this thesis are :

1. The first constant factor approximation algorithms and complexity results for the max-coloring problem on bipartite graphs, interval graphs and an any hereditary class of graphs.

2. An improved analysis of the well studied first-fit coloring algorithm for interval graphs.

3. An experimental evaluation of new heuristics for the max-coloring and interval coloring problem on chordal graphs.