Lesson 4

Typical applications of graph coloring include problems where there is a limited amount of resources (colors) and a number of constraints of the form “these two objects cannot share the same resource”. We give a number of examples below.

• Exam timetabling.  During a semester, each student attended a number of courses. Now we would like to create an exam schedule ensuring that no student has exams for two courses on the same day. What is the minimum number of days needed to conduct all exams?
  This problem can be modeled as the graph coloring problem as follows. Create a graph whose nodes are courses. Join two courses by an edge if there is a student who attended both these courses. Then, the chromatic number of this graph is the minimum number of days needed to organize the exams on all courses.


• Register allocation.  In addition to RAM, a computer usually has some ultra-fast memory cells called registers. Registers are expensive and scarce (about thirty). An optimization during the compilation process is to store variables in registers if their values are needed repeatedly.
  One can find the minimum number of registers needed by modeling this problem as the following graph coloring problem. For each variable, define its lifetime interval (roughly from declaration to the last use) and build an interference graph: intervals are connected if they overlap (that is, the same register cannot be used for both variables). Then, the chromatic number of this graph is the minimum number of registers. Interestingly, whereas finding a chromatic number of a graph is a difficult problem in general, it can be solved efficiently for this class of graphs (called interval graphs).


• Radio frequencies allocation.  If two radio towers are close, they must use different frequencies. What is the minimum number of frequencies needed? It is straightforward to model this problem as the graph coloring problem. A more general problem requires neighboring towers to differ significantly in frequency.


• Excursion organizing.  You want to send a large group of people on a trip, but some pairs of them dislike each other so much they won't ride the same bus. What is the minimum number of buses required?


• Puzzles.  Some puzzles are variants of graph coloring. For example, the Sudoku puzzle may be viewed as a partially colored graph: connect two cells if they're in the same row, column, or \(3 \times 3\) block. Then, the task is to extend the given coloring to a proper \(9\)-coloring of the corresponding graph.