algorithmsdiscrete mathematicsgraph theory
I am trying to prove that for any Graph there is an ordering of the vertices, sucht that the Greedy Algorithm will colour the vertices in such a way that it uses the Chromatic number of colours.
I am trying to attack this via induction, and I have the impression I am nearly there. However I ve been waisting quite a bit of time trying to make the inductive step solid, so I was wondering, whether somebody knows if my strategy can even potentially work ?
The conclusion would be that the greedy algorithm isn't optimal, in other words, it sometimes colors the graph in more than the minimal number of colors. One may ask whether a better algorithm exists. This leads to the concepts of NP-completeness, approximation algorithms and hardness of approximation.
There is a graph called the crown graph which is an excelent counterexample. Consider the bipartite graph with vertex set $\{v_1,v_2,\dots ,v_{2014},u_1,u_2,\dots ,u_{2014}\}$ where two vertices are adjacent if they have different letters and different numbers, now order them in the following manner: $v_1,u_1,v_2,u_2,\dots ,v_{2014},u_{2014}$. the algorithm will assign the same color to $v_1$ and $u_1$ since they are not adjacent, it will then have to assign a different color to $v_2$ since it is adjacent to $u_1$ and it will then assign the same color to $u_2$ which will cause it to use yet another color for $v_3$ since it is adjacent to $u_1$ and $u_2$ however it will give this same color to $u_3$ and it will proceed like this until it has used $2014$ colors.
Here is an image from wikipedia:
Best Answer
Of course there is such an ordering - if you have the optimal coloring, order the vertices st. first come the vertices of color 1, then vertices of color 2, ...
Is this what you wanted to know?