Date of Degree
PhD (Doctor of Philosophy)
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.
Copyright 2007 Rajiv Raman
Raman, Rajiv. "Chromatic scheduling." dissertation, University of Iowa, 2007.