1
$\begingroup$

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 Answers 1

2

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?

  • 0
    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)2012-02-07
  • 1
    @Beltrame why did you accept an answer you are not satisfied with?2013-06-27
  • 1
    @Beltrame See this answer for a better explanation: https://math.stackexchange.com/a/1114334/76284.2018-02-28