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?