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. The goal is to avoid giving two adjacent (linked by an edge) vertices the same color.

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 not all vertices are colored, sequentially build color classes by trying to include uncolored, non-adjacent vertices (in the given order) in the current class.

I am almost sure that these two algorithms are equivalent. Indeed, consider Algorithm 2 on a graph with 5 vertices. Suppose the first color class has vertices 1, 3, 5. This means that vertices 2 and 4 cannot take color 1. So in Algorithm 1, vertex 1 would take color 1, vertex 2 would take color 2, vertex 3 would take color 1, vertex 4 would take color 2 or 3, and vertex 5 would take color 1. This simple example convinces me it is true, but of course it is not a proof. Can we transform it into a proof by making it more generic, or can we find a counter example?

• Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask
– gnat
Nov 3, 2015 at 23:15
• Your question description is missing something - are you talking about an algorithm for coloring vertices so every two connected vertices get a different color? Nov 4, 2015 at 6:44
• @gnat: after the last edit, the OP tried indeed to tell us what he had tried to solve the problem. But the description is IMHO too incomplete to give him a reasonable answer. Nov 4, 2015 at 10:20
• This question may also be a fit for math or cs stack exchanges Nov 4, 2015 at 12:50
• @DocBrown Indeed, by "available color" I mean one that does not color two adjacent (linked by an edge) vertices. Nov 4, 2015 at 15:01