Optimizing Schedule of Boarding School Using Vertex and Edge Coloring Approach:
A Case Study of Sekolah Menengah Sultan Abdul Halim, Jitra, Kedah
Soft skills like time management, teamwork and effective
communication are highly important nowadays. But, many students
are still lack of knowledge regarding all these skills. It is because,
students are too much concerned with academic excellence until they
neglect the mastery of the skills that they should have. This study
focused on one of the boarding schools in Malaysia located in Kedah
known as Sekolah Menengah Sultan Abdul Halim (SMSAH). The aim
was to increase the awareness of the importance of soft skills within
themselves. The important of this study in order to achieve this goal is
to optimize the school schedule using the Graph Coloring method. In
this study, two approaches have been used under the Graph Coloring
method which are Vertex and Edge Coloring. Greedy Algorithm has
been used to solve the Vertex Coloring approach while Graph Coloring
Algorithm has been used to solve the Edge Coloring approach. The
algorithm that produced the lowest minimum color will be selected for
implementing the schedule of the boarding school. The result has
shown that the Greedy Algorithm has succeeded to produce the very
minimal color for the boarding school scheduling.
Traditions: Lessons from Indonesia and Malaysia,” J. Pendidik. Islam, vol. 10, no. 1, pp. 67–88,
 A. N. Mansor, J. Sanasi, M. Y. M. Nor, N. M. Nasir, and J. A. Wahab, “Teacher perceptions of
managing indiscipline amongst at-risk teenage students: A Malaysian study,” Int. J. Adv. Appl. Sci.,
vol. 4, no. 5, pp. 112–119, 2017.
 S. Majid, C. M. Eapen, E. M. Aung, and K. T. Oo, “The importance of soft skills for employability
and career development: Students and employers’ perspectives,” IUP J. Soft Ski., vol. 13, no. 4,
pp. 7–39, 2019.
 R. Hoshino and I. Fabris, “Optimizing student course preferences in school timetabling,” in
International Conference on Integration of Constraint Programming, Artificial Intelligence, and
Operations Research, 2020, pp. 283–299.
 C. S. de Barros, G. G. Mendonça, A. H. Gameiro, and others, “Farm-Boarding School
Management: Linear Programming Contributions in the Search of Self-Sufficiency and
Optimization,” J. Agric. Sci., vol. 9, no. 3, 2017.
 N. D. Jalil, M. Masrom, and W. N. W. Zakaria, “A mathematical model of healthy diet menu plan
for MARA Junior Science College boarding schools,” Morb. Mortal., vol. 32, no. 1, pp. 13–18, 2017.
 A. M. Sudin and S. Sufahani, “Optimization Technique With Sensitivity Analysis On Menu
Scheduling For Boarding School Student Aged 13-18 Using ‘Sufahani-Ismail Algorithm,’” in Journal
of Physics: Conference Series, 2018, vol. 995, no. 1, p. 12047.
 N. A. Halim, N. A. Harun, N. M. Kenali, S. S. M. Sopie, and others, “Oral Health Knowledge, Attitude
and Practice of the Caregiver at the Special Needs Boarding School in Kuantan, Pahang,” Age
(Omaha)., vol. 11, no. 30, pp. 26–28.
 N. Norlia and M. Mastura, “Relationship between attitude, subjective norm, and perceived
behavioural control of learning practices among boarding school students,” J. Couns. Educ.
Technol., vol. 3, no. 1, pp. 23–28, 2020.
 S. Wang and D. Zhang, “The impact of time while boarding on students’ academic achievement
and social emotional competence: A propensity score matching analysis,” Stud. Educ. Eval., vol.
65, p. 100851, 2020.
 F. Rahmi, R. Hasnida, and L. H. Wulandari, “Effect of Academic Resilience on Subjective Well-
Being of Students in Islamic Boarding Schools,” Int. Res. J. Adv. Eng. Sci., vol. 4, no. 3, pp. 347–
 S. A. Dean, “Soft skills needed for the 21st century workforce,” Walden University, 2017.
 M. A. Mosa, A. Hamouda, and M. Marei, “Graph coloring and ACO based summarization for social
networks,” Expert Syst. Appl., vol. 74, pp. 115–126, 2017.
 R. Ganguli and S. Roy, “A study on course timetable scheduling using graph coloring approach,”
Int. J. Comput. Appl. Math., vol. 12, no. 2, pp. 469–485, 2017.
 E. Papaioannou, S. Athanassopoulos, and C. Kaklamanis, “Efficient course and exam scheduling
using graph coloring,” Int. E-Journal Adv. Educ., vol. 3, no. 7, pp. 51–59, 2017.
 A. Parihar, N. Shukla, M. Jerry, S. Datta, and A. Raychowdhury, “Vertex coloring of graphs via
phase dynamics of coupled oscillatory networks,” Sci. Rep., vol. 7, no. 1, pp. 1–11, 2017.
 Y. Cao, G. Chen, G. Jing, M. Stiebitz, and B. Toft, “Graph edge coloring: A survey,” Graphs Comb.,
vol. 35, no. 1, pp. 33–66, 2019.
 A. Y. Ali, “Greedy algorithm for solving student allocation problem in internship program: a case
study,” Int. J. Res. Ind. Eng., vol. 10, no. 2, pp. 155–164, 2021.