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?

  • 1
    @Beltrame See this answer for a better explanation: https://math.stackexchange.com/a/1114334/76284.2018-02-28