Are these graph coloring algorithms equivalent? Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices.
I am wondering if these two algorithms are equivalent:
Algorithm 1: Consider each vertex (in the given order) and assign the smallest color available.
Algorithm 2: While all vertices are not colored, sequentially build color classes by trying to include vertices (in the given order) in the current class.
I am almost sure that these two algorithms are equivalent, but a confirmation would be great! Thanks. 
 A: Assuming that your second algorithm does the following: For each colour $i\in [1,c]$ in order, go through the vertices $v_1,\ldots, v_n$ in order and assign to a vertex the colour $i$ if it is not already coloured, and no neighbour of it has colour $i$.
Let us suppose for contradiction that algorithm II doesn't produce the same colouring as algorithm I, let us call these colourings $c_1$ and $c_2$. There is some smallest colour $i$ which appears in the wrong place, and some smallest vertex $v_j$ given the colour $i$ by algorithm II where algorithm I give $v_j$ a different colour. That is $c_2(v_j) = i$ and $c_1(v_j) \neq i$. That is, we assume that for all $i'<i$ and $v_k$ if $c_1(v_k)=i'$, then $c_2(v_k)=i'$ and also if $v_k < v_j$ and $c_1(c_k) = i$, then $c_2(v_k)=i$.
However, since $c_1(v_j) \neq i$ either there is a neighbour $v_k$ of $v_j$ with $v_k < v_j$ and $c_1(v_k)=i$ or $c_1(v_j)=i' < i$ and so $v_j$ has no neighbour coloured $i'$ in $c_1$. In the first case, $c_2(v_k)=i$ and so we can't also colour $c_2(v_j)=i$, contradicting our assumption. In the second case we can conclude that $v_j$ has no neighbour coloured $i'$ in $c_1$ and hence no neighbour coloured $i'$ in $c_2$, and so when we tried to colour $v_j$ with colour $i'$ in algorithm II, which happens before we try to colour it with colour $i$, we were succesful, again contradiction our assumption.
