Conflict-Free Academic Scheduling: A Graph Theory Approach to University Timetabling and Resource Optimization

This study investigates the use of graph coloring algorithms to optimize academic timetabling and resource allocation in higher education institutions. By modeling courses as vertices and scheduling conflicts as edges, graph-based techniques such as Welsh–Powell and Greedy Coloring were applied to real-world data from a university in Chennai. The analysis revealed that graph coloring significantly reduced scheduling conflicts, improved classroom utilization, and provided a scalable alternative to manual timetable creation. Statistical validation through a paired sample t-test confirmed a notable improvement in scheduling efficiency. The study concludes that graph coloring offers a practical, data-driven solution for conflict-free, optimized academic scheduling and is especially useful for institutions aiming to modernize their administrative processes.