Courses Scheduling using Graph Labeling

Abstract

At the beginning of each academic semester, universities are routinely required to develop course schedules that minimize or eliminate conflicts. Scheduling conflicts typically arise when multiple courses are taught by the same lecturer, taken by the same group of students, or require the use of the same classroom. As a result, an efficient and systematic method is needed to generate conflict-free schedules while optimizing the use of available time slots. One alternative approach is to apply graph theory, particularly graph coloring techniques, to the scheduling process. In this approach, each course is represented as a vertex in a graph, and an edge is established between two vertices if the corresponding courses cannot be held simultaneously. Graph coloring is then used to assign different time slots (represented as colors) to adjacent vertices, ensuring that no conflicting courses are scheduled at the same time. This paper proposes a course scheduling algorithm based on graph coloring, aiming to produce feasible schedules that reduce conflicts and enhance resource utilization. The approach provides a mathematical framework that can support automated and scalable scheduling systems in academic institutions.