A timetablesystem based on graph coloring

Abstract

Graph theory is an important branch of Applied Mathematics with numerous applications to solve practical problems in Electrical networks, Circuit layout, Data structures, Operations research and Social sciences.

Graph coloring is one of the most important areas of graph theory. The chromatic coloring problems of the graph is related to many problems of matching such as the assignment of crews to work centers, time tabling problems of crews, exam scheduling etc.

This paper presents graph coloring and room allocation algorithms and shows how these two algorithms can be combined together to provide a basis of a flexible and widely applicable time tabling system. Such problems are formulated. in a mathematical model and the solutions are obtained by using a computer program in Visual Basic language. How several common timetabling features can be handled within the system is also discussed in detail.