Application of the Welch-Powell Graph Coloring Algorithm for Optimizing Course Scheduling Using Python (Case Study: Computer Science Program, Faculty of Mathematics and Natural Sciences, HKBP Nommensen University, Pematangsiantar) - Ropitta Anjelina Manik; Juli Antasari Sinaga; Gayus Simarmata (Indonesian Journal of Advanced Research, 2026)
Course scheduling is the process of assigning courses to specific time slots and classrooms while taking into account various applicable academic constraints. This study discusses the application of graph theory in the development of a course schedule for the Computer Science Program at the Faculty of Mathematics and Natural Sciences (FMIPA). The main problem in course scheduling is schedule conflicts caused by instructors teaching more than one course. To address this problem, the graph coloring method using the Welch-Powell algorithm is employed. Each course is represented as a vertex, while scheduling conflicts between courses are represented as edges based on shared instructors. The research process begins with the construction of a conflict graph, the determination of vertex degrees, and the sorting of vertices by highest degree, followed by the graph coloring process using the Welch-Powell algorithm. The coloring results show that course schedules can be grouped into several colors representing class days without causing conflicts in faculty schedules. Semester 2 requires 4 colors, semester 4 requires 5 colors, semester 6 requires 6 colors, and semester 8 requires 2 colors. The research results show that the graph coloring method using the Welch-Powell algorithm is capable of producing a more structured and effective class schedule while minimizing faculty schedule conflicts. Thus, the application of graph theory can serve as an alternative solution in the process of developing class schedules in higher education settings.