Without investigating in depth the numerous and important matters related to coloring in graphs, we will give the theoretical results necessary for solving a nice application to a timetabling problem.

Coloring problems

Historically, with the four-color theorem mentioned in Basic Concepts, it is a coloring problem which is at the origin of graph theory. This concerned the problem of coloring the vertices of a planar graph. The general issue is to find the chromatic number of a graph, planar or not. This is the lowest number of colors needed to color the vertices so that no two adjacent vertices have the same color. There are a few known applications of this type of graph coloring. However, coloring of edges is also considered, and we are going to study this here because it presents an interesting application to a timetabling problem, and because it also relates to another important matter in graph theory: matchings (studied in Chapter of Matchings).

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(71)