A timetable scheduling using the graph coloring approach

Abstract

This research presents a lecture timetable scheduling system using graph coloring techniques, specifically edge coloring in bipartite graphs. For each subject separate bipartite graphs were constructed with lecturers and subjects forming two sets of vertices, and edges representing teaching assignments. Edge coloring assigned time slots, with multiple colors for multi-credit courses and special handling for practical classes (six hours weekly, we assign 3 hours per week, regardless of credit or hour distribution. Each practical course is allocated a total of 6 hours per week, with 3 hours for Group 1 and 3 hours for Group 2. A student can take a maximum of 3 main subjects. Even if a student takes 3 practical courses, there will never be a conflict in the practical schedule). Some subjects were allowed to share time slots, while others required distinct slots to avoid conflicts. Instead of building a single unified graph, the final timetable was manually integrated from the edge-colored subject graphs. The system met academic requirements for credit hours and ensured students could enroll in for up to three main subjects without clashes. This study shows that edge coloring in bipartite graphs provides a structured and effective method for timetable scheduling. It highlights the practical applicability of graph theory in solving real-world academic scheduling problems and lays the groundwork for future automation of the process. This study uses graph colouring to create clear, flexible, and conflict-free timetables. It also improves scheduling by allowing 2 credit subjects to be split, making the process easier, faster, and more efficient than the manual method