The term colouring is a little confusing (is this a problem you wrote yourself?). I suppose you mean: find a minimum cardinality set S such that for each vertex v, either v is in S or at least one of v's neighbours is in S. This problem is not equivalent to the maximum independent set problem. It seems to be NP-hard, so you might try to prove it if all of your attempts to find a polynomial time algorithm have failed.
> Hello > > I came across the following problem which i am unable to solve : > > Given a Graph G. we have to find the minimum number of vertices that > should be colored so that each vertex is > > either colored or has a neighbouring vertex which is colored. > > Please help --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
