Graph Coloring Problems

This chapter presents the basic concepts of colorings as well as a series of variations and generalizations prompted by various scheduling problems including drawing up school timetables. It gives an outline of methods based on the Tabu search for finding approximate solutions for large problems. An additional advantage of the Tabu algorithm is that it is relatively easy to adapt it to various graph coloring problems. The class of perfectly orderable graphs is interesting with regard to coloring because of the simplicity of the exact coloring algorithm. While coloring problems are generally hard for arbitrary graphs, the class of perfect graphs has the particularity of containing graphs for which the chromatic number can be calculated in polynomial time. When formulated in terms of graph coloring, the scheduling problem given at the beginning of the chapter belongs to the domain of chromatic scheduling.