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
