International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Since Year 2012 | Open Access | Double Blind Reviewed

ISSN: 2319-7064




Downloads: 125 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1

Research Paper | Computer Science & Engineering | Sri Lanka | Volume 8 Issue 12, December 2019


An Application of Graph Coloring Model to Course Timetabling Problem

Wathsala Samarasekara


Abstract: This paper studies the problem of developing an automated timetable using graph coloring model which is applicable to course timetabling problem in higher education institutes. Constructing a satisfactory conflict-free semester-long timetable of courses is often a difficult problem that any institute faces each semester. Construction of such type of timetable can be modeled as a graph coloring problem. In a graph coloring model, the timetabling problem is usually represented as a graph where events are represented as vertices, while conflicts between the events are represented by edges. Edges of a graph are colored and each time slot in the timetable corresponds to a color in the graph coloring problem. After finding time slots, the possible courses can be conducted in each time slot are assigned according to the graph. Finally, separate timetables for each academic year are filled by assigning each subject for available time periods according to the proposed algorithm. The automated timetabling system is based on the proposed algorithm of the graph coloring model. The proposed system can generate not only one solution for the timetabling problem, but also many possible solutions. Therefore this timetabling system exhibits a much better quality of solution.


Keywords: Timetabling Problem, Graph Coloring, Algorithm, Automated


Edition: Volume 8 Issue 12, December 2019,


Pages: 1583 - 1591


How to Cite this Article?

Wathsala Samarasekara, "An Application of Graph Coloring Model to Course Timetabling Problem", International Journal of Science and Research (IJSR), Volume 8 Issue 12, December 2019, pp. 1583-1591, https://www.ijsr.net/get_abstract.php?paper_id=ART20203698

How to Share this Article?

Enter Your Email Address




Similar Articles with Keyword 'Graph Coloring'

Downloads: 103

Survey Paper, Computer Science & Engineering, India, Volume 4 Issue 9, September 2015

Pages: 1656 - 1659

A Survey on Graph Partitioning Techniques

Santosh Nage | Girish Potdar [2]

Share this Article

Downloads: 153

Research Paper, Computer Science & Engineering, Indonesia, Volume 7 Issue 11, November 2018

Pages: 1692 - 1697

Using Graph Coloring for University Timetable Problem

R. Kristoforus J. Bendi | Theresia Sunarni | Achmad Alfian

Share this Article


Top