Question $2$: Coloring a Graph $.......................................................[10]$

In the Graph Coloring problem, you are given an undirected graph $\backslash ($ G$=($V$,$ E$)\backslash ),$ and the goal is to color the vertices using $\backslash ($ k $\backslash )$ colors $($think of $\backslash ($ k $\backslash )$ as a given parameter$)$ such that any two neighboring vertices are colored with different colors. I.e$.,$ for every edge $\backslash ($ u v$,$ u $\backslash )$ and $\backslash ($ v $\backslash )$ are assigned different colors.

Suppose all the vertices have degree $\backslash (\backslash$leq D $\backslash ),$ for some parameter $\backslash ($ D $\backslash ),$ and let $\backslash ($ k$=$D$+1\backslash ).$ Consider the following local search algorithm:

$1.$ Start by assigning an arbitrary color to each vertex.

$2.$ While there exists a vertex $\backslash ($ u $\backslash )$ that has a "conflict" $($i$.$e$.,$ some neighbor that has the same color as $\backslash ($ u $\backslash ))$:

$($a$)$ Find some color $\backslash ($ c $\backslash )$ that does not conflict with any neighbor of $\backslash ($ u $\backslash )$ and color $\backslash ($ u $\backslash )$ using $\backslash ($ c $\backslash ).[$Why is this always possible? that is the first part!$]$

$3.$ Return the obtained coloring.

You will now analyze this algorithm.

$($a$)[2]$ Give a line of explanation as to why the choice $\backslash ($ k$=$D$+1\backslash )$ ensures that step $2$a of the algorithm is always feasible.

$($b$)[3]$ Define an "objective" function for a given coloring, as the number of vertices having a conflict with some neighbor. What happens to the objective in each step of the While$()$ loop in step $2$ of the algorithm?

$($c$)[5]$ What is the overall running time of the algorithm? $[$Note: You must describe how you would keep track of the colors in step $2$a$,$ as that plays a role in the running time.$]$