The sequential algorithm for coloring graphs is as follows
- Put vertices in the queue $ v_1,v_2,...,v_n$ in the order of your choice.
- 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?