Vertex order for Greed coloring of a Graph

Question

I'm interested in coloring the graph $G$ with the greedy algorithm. Now I know that the result can depend on the vertex order and can also be very bad. Now I want to show that there is a vertex order for which the Greedy algorithm gives an optimal result. Intuitive I understand that if there is a perfect coloration for $G$ then you take it and arrange the vertex in ascending colors. But how can I formally prove that the coloration provided by the greedy algorithm with this vertex order is really less than or equal to the given coloration ?

Answer 1

Just check what happens during execution of the algorithm.

You have colors $c_1,\ldots,c_k$ and you list the vertices according to their color classes $X_1,\ldots,X_k$, i.e. all vertices of $X_i$ have color $c_i$. The order of the vertices within one color class does not matter. Now the color classes form independent sets, so as long as you are coloring vertices of $X_1$, you will always use color $c_1$.

If you start coloring vertices of $X_2$, you may still be able to use color $c_1$(!), but you will certainly always be able to use color $c_2$, since all previously colored vertices either have color $c_1$, or they are in $X_2$, which is an independent set.

The general idea is that you never need to use color $c_i$ before you are coloring vertices of $X_i$. I trust you can extend this idea to a proper proof using induction.