Sequential algorithm for coloring graphs- there exists an ordering of vertices where it finds a coloring with $\chi(G)$ colors.

Question

The sequential algorithm for coloring graphs is as follows

1. Put vertices in the queue $ v_1,v_2,...,v_n$ in the order of your choice.
2. Take out vertices from the queue and color them with the lowest color (think of colors as numbers) that's not used by their neighbours.

Meaning for example:

I need to prove that for every graph there exists an ordering of the vertices, that the algorithm finds the coloring with $\chi(G)$ colors.

Well traditionally I tried induction by the number of vertices.

When $|E(G)|=m$ our consists of a single vertex, which is colored with $1$ so all is good.

Now for the induction step.

We have a graph $G$ with $n+1$ verices. Let's take out the one with the highest degree out of it - let's name it $v$. We get a graph $G-v$. Given the proper ordering of vertices in $G-v$ the algorithm find the coloring of it with $\chi(G-v)$ colors. Obviously $\chi(G-v) \leq \chi(G)$. Now we have two cases.

Either $deg(v)<\chi(G-v)$, then we can color it with some of the colors used in $G-v$ and all is good, we can't go with less colors then $(G-v)$. Now if $deg(v)>\chi(G)$ Then let's inspect the neighbours of $v$. If the colors that they use are not all from $G-v$ then we can also color it how we want. But if the colors they use are all of the colors used in $G-v$ then we have to add one more, which is optimal.

Is this in any way correct?

Answer 1

Given a minimal coloring $c:V(G)\rightarrow\{1,2,\ldots,\chi(G)\}$, simply order the vertices in the queue so that all the vertices with $c(v)=1$ come first, followed by those with $c(v)=2$, and so on. When the vertices are removed from the queue, each will be assigned a new color $c'(v)$. Since none of the vertices with $c(v)=1$ are adjacent to each other, they will all have $c'(v)=c(v)=1$. Next, none of the vertices with $c(v)=2$ are adjacent to each other, so they will all have either $c'(v)=1$ (if they have no neighbors in the first batch) or $c'(v)=2$; that is, $c'(v)\le c(v)$ for $c(v)\le 2$. And so on, by induction; we conclude that $c'(v) \le c(v)$ for all $v$. So $c'$ has no more colors than $c$; and since $c$ was already a minimal coloring, $c'$ must have exactly $\chi(G)$ colors.