The graph coloring problem requires one to color the vertices in a graph so that no two adjacent

vertices have the same color. The goal is to minimize the number of colors used.

In the greedy coloring algorithm below, each vertex is numbered from $1$ to $|$V $|$ and each color is

represented by a positive integer. The algorithm tries to minimize the number of colors used,

k$,$ by greedily coloring each vertex i with the $$smallest$$ color, c$($i$),$ that hasn$$t been used by

any of its neighbors, N$($i$),$ thus far. Sometimes, this increases the number of colors used. After

coloring each vertex, it returns k