Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
There's really no need to use the symbols $\forall, \exists$ when ordinary English would be much more readable. – Qiaochu Yuan Feb 7 '12 at 23:29
up vote 2 down vote accepted

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.

share|cite|improve this answer
I had a discussion with my Professor about this rather vague question today, and apparently a discussion along these lines is pretty much all that was expected. ( which at the point the question was posed didn't make too much sense to me, as it had already been shown, that the order in which vertices have to be passed to the greedy algorithm has to be chosen very carefully if one wants to ensure optimal colouring; i.e. the potential suboptimality had already been firmly established, but there you go....) – Beltrame Feb 8 '12 at 18:18

Your Answer


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.