Problem $4-20$ marks

The Graph$-$Coloring problem is defined as follows:

Given an undirected graph $G=(V,E),$ where $V$ is the set of vertices and $E$

is the set of edges, the graph coloring problem is to assign colors to the vertices

in such a way that no two adjacent vertices have the same color.

Let:

$V=\{v_1,v_2,$dots,$v_n\}$ be the set of vertices.

$E=\{e_1,e_2,$dots,$e_m\}$ be the set of edges.

$C=\{c_1,c_2,$dots,$c_k\}$ be the set of colors.

The graph coloring problem can be mathematically formulated as follows:

Minimize $|C|$

subject to the constraint:

$AA{e}_i=(v_a,v_b)inE,c(v_a)c(v_b)$

Now take the following problem:

Suppose we want to schedule exams for $n$ courses. The obvious require$-$

ment is that no student should have two exams at the same time$-$slot. This

corresponds to scheduling exams for the courses that have common students in

different time$-$slots. We want to determine the minimum number of time$-$slots

needed to cater to everyone. Show that this is an NP$-$complete problem be

reduction via Graph Coloring.