Comparison with the greedy algorithm Consider the following algorithm to vertex coloring:
First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining graph and color those 2, and so on. Compare this algorithm with the greedy algorithm: which is better?
I've given it some thought but I still can't get started with this problem, can you sketch a solution? It's a homework question
 A: To compare the algorithms you need to specify how you are obtaining the independent set. For the sake of completeness, these are the algorithms:
GREEDY : Take an ordering of vertices $v_1,v_2,....v_n$. Color each vi with smallest integer not used to color its neighbours from $v_1$ to $v_i-1$
INDEPENDENT SET : Take an ordering of vertices $S = [v_1,v_2,.....v_n]$. To create independent set, pick $v_1$ and add it to $I = ${}. From $S$, repetitively pick $v_i$ with smallest index not adjacent to any vertex in $S$. Give them a color and remove them from $S$. Repeat until $S$ is empty.
To compare the algorithms, let us take same ordering of vertices.
Consider all the vertices you assign color $1$ by greedy algorithm. By using independent set algorithm, in iteration $1$, we get $I$ as the set of vertices assigned 1 as they don't have edges between them and any other vertex has at least one of the color $1$ vertices as their neighbours (as otherwise they would've been given color $1$). Similarly, in the $i$th iteration of Independent set algorithm, we get vertices colored $i$.
Hence, both the algorithms give the same output for a given ordering.
P.S. "better" here refers to no. of colors as the chapter the question is derived from doesn't deal with time and space complexities.
