Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.