A novel graph coloring algorithm for solving the exam scheduling problem

Graph coloring is one of the popular constraint satisfaction problems (CSP). CSPs are quite practical, but they’re usually of NP-hard degree. Recently, considering the fast growth of big data tasks and massive inputs of these tasks, NP-hard solutions became just more impractical than ever. In this paper we propose a new graph coloring algorithm which relies on logical calculations for labeling instead of arithmetic in order to gain polynomial time-complexity. While dividing graph into several bipartite sub-graphs, we also use approximations in binary labeling, choosing head vertices for BFS and matching the final colors. As a case study, we implemented our algorithm on a graph obtained from MAZUST course selections. From this new point of view, we can color the graph in very short run-times with O(V+E). Also improving aforementioned approximations in future works can significantly enhance the outcome without adding much to the time complexity. We are hopeful that ideas in this paper will lead to developing a fully optimal graph coloring algorithm of polynomial time complexity for at least the planar graphs.