Dissecting Graph Coloring Problem

Graph Coloring is one of the interesting NP Complete problems. However, it is not just an interesting but challenging puzzle to solve; just like many classic computer science problems, it also has many real-life applications.

For instance, consider a scenario of a University exam. Students take many courses and it is important to ensure that no two courses with overlapping students have exams scheduled at the same time. On the contrary, if two courses do not have any common students, they can be scheduled at the same time. The question here is what is the minimum number…