Applying Graph Coloring To Schedule Doctors' Work In A Hospital.


  • Ferdous Omar Taoufic King Saud University



Graph coloring, doctor's roster, greedy algorithm.


Scheduling shifts is a tiresome and time consuming task in any business, and particularly in hospitals where errors are costly, rules are plentiful and changes are rapid. The person performing this function (Rota Organizer) will have to keep track of all the employees concerned, distributing hours fairly and avoiding collisions. Rules regulating working hours and breaks have to be followed and the qualifications of individual employees need to be considered. Hours are spent every day on this task in every ward. The goal of this paper is to solve Doctors Scheduling Problem (DSP) and initialize a fair roster for two wards of Pediatric Department (PD) in Prince Sultan Military Medical City (PSMMC) in Saudi Arabia. So to find a solution of DSP, we used Graph Coloring which is one of the methods used mostly to solve this problem.


Download data is not yet available.


1. Amponsah, S.K, Agyeman, E., Okran, K.G. 2011. Graph Coloring, an Approach to Nurses Scheduling. American- Eurasian Journal of Scientific Research 6(1). Ghana, 1-5.
2. Butt, R. 2007. Introduction to Numerical Analysis Using Matlab. USA.
3. Diestel, R. 2000. Graph Theory. Springer-Verlag, New Your, 98-103.
4. Gideon, A. 2013. A Nurse Scheduling Using Graph Coloring. Master thesis submitted, Mathematics Department, Kwame Nkrumah University, Ghana, 1-4, 35, 53-77.
5. Harju, T. 2011. Graph Theory. Lecture Notes in Mathematics, Finland, 53-60.
6. Kumara, B.T.G.S., Perera, A.A.I. 2011. Automated System For Nurse Scheduling Using Graph Coloring. Indian Journal of Computer Science and Engineering (IJCSE), 476- 485.
7. Rosen, K. 2012. Discrete Mathematics and It's Applications. New York.
8. Rosen, K. 2009. Chromatic Graph Theory. Michigan.
9. Shekhar, S. 2012. Graph Theory. Lecture Notes in Mathematics, US, 137-139.
10. Skogvold, A.; Saether, T.; Moseby, S.; Westby, P. 2009. Flexible Duty Roster for Doctors in Hospital, 1-3.
11. West, D. 2001. Introduction to Graph Theory. New Jesey.
12. Wilson, R. 1996. Introduction to Graph Theory. England.
13. Wren, A., Scheduling. 1996. Timetabling and Rostering- a Special Relationship?. Lecture Notes in Computer Science. Springer-verlag, Berlin, 46-75.
14. Dharwardker,A., 2006. The Vertex Coloring Algorithm. Available at: < g/>, (March 2016).
15. Greedy Coloring Algorithm. August 2015. Available at: < NIpSE >, (May 2015).




How to Cite

Taoufic, F. O. (2016). Applying Graph Coloring To Schedule Doctors’ Work In A Hospital. JOURNAL OF ADVANCES IN MATHEMATICS, 12(11), 6840–6844.