algorithmsdiscrete mathematicsgraph theory
So I have shown, that for all n $\in N $ there is a graph $G$ with n vertices such that the Greedy Algorithm will colour it in exactly 2 colours.
Further I have shown that for a Graph with diameter at least 3 there is an ordering of the vertices such that the Greedy Algorithm uses at least 3 colours. (both rather trivial tasks admittedly.)
Apparently these 2 rather basic insights should give me some more interesting property though, and I m wondering what that could be.
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
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?
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
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.