# Existence of Vertex Ordering in Greedy Algorithm to get “optimal” colouring

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 ?

-

## 1 Answer

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?

-
not really, we may be talking about different greedy algorithms. Let me think about it though, would be cool if it s really that trivial ! (and I d have waisted a lot of time lol) – Beltrame Feb 7 '12 at 15:47
@Beltrame why did you accept an answer you are not satisfied with? – Tomas Jun 27 '13 at 1:26