Are these graph coloring algorithms equivalent?

Question

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?

Answer 1

I think you are correct, both algorithms are equivalent. Look which of the vertices of an arbitrary graph get the first (smallest) color C1 from both algorithms. It is easy to see that those are the same, because both algorithms do essentially the same - iterate over the vertices in the given order, assign either C1 or

• a different color (algorithm 1)

• no color (algorithm 2)

to a vertex, with the constraint to use C1 when the next vertice is not adjacent to a formerly C1-colored vertex.

Now you can apply the same argument for the next color C2, using all not C1-colored vertices, then C3 and so on, which leads you inductively to the same total coloring.