2
$\begingroup$

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.

  • 2
    There's really no need to use the symbols $\forall, \exists$ when ordinary English would be much more readable.2012-02-07

1 Answers 1

3

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.

  • 0
    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....)2012-02-08