Graph Theory (III)

One of the largest topics within Graph Theory is that of Graph Colouring. Formally, a proper graph colouring is an assignment of labels, or "colours" to the vertices of a graph, so that no adjacent vertices share the same colour. The chromatic number of a graph is the smallest number of such labels that can be used to properly colour it. Consider the following assignment problem: A university has to offer certain classes in the next semester. Each specific class will be taught by a specific professor and at a specific time-slot in the day. Naturally, this means that two classes taught by the same professor, must not be offered at the same time; he can not be in two places at once. Furthermore, each class will have specific students who wish to take it. This means that if two classes will be taken by the same student, they also cannot be offered at the same time. The question then becomes, how can we assign the classes? What is the minimum number of time-slots that the university will need to use, to offer all its classes?

This question can be answered by using the idea of Graph Colouring. We draw a graph, as follows: The different classes to be offered, will be our vertices. The classes that cannot be offered together, either because they are taught by the same professor, or because they share a student, are connected together. Then, the given problem is simplified to finding a proper colouring of the graph, where the labels used will represent the time-slots. And, of course, if we want the smallest number of time-slots needed, we must find the chromatic number of the graph.

In practice, this sort of problem is far more complex, as it takes into account multiple sections, classroom availability, number of students expected to need the course and so forth. Also, the restriction on classes sharing a student is generally changed to a restriction on classes expected to share a significant number of students and only offered as single sections. Nevertheless, all problems of resource assignment can be represented as graph colouring problems. In addition to this, many other problems can be studied via Graph Colouring, particularly the all-important class of NP-Complete problems.

The name "colouring" originates in a rather old question: Given a map of a region, how many colours are needed to colour it, if no two adjacent regions (i.e. regions sharing a border) can have the same colour? The surprising answer is "no more than four". The proof for this is extremely long and complicated, which tells us that the field of Graph Colouring is a very deep one indeed.