Ok your question have some little catch hidden. But first let me was the question. Does each vertex has at least one forbiden color? because if you can have no forbiden colors you end up with clasical 3-coloring problem which is NP-Complete.
The catch is that if P=NP then everything nontrivial is NP-Complete by definition of NP-Completeness. So the possible cases are that you prove that it is in P, or you can prove that it is NP-Complete. I suggest first by coloring each vertex by forbiden color +1 modulo 3, and then you have some components that violate the coloring, but they must be 2 colorable. For connected component there are only 2 possible bicolorings. So you color each component by new colors Black and white. name the coloring default and nondefault I feel that this leads to some 2-sat :D because if i choose default coloring of component A, I can not use default coloring for B is A => ~B what is ~a or ~B or you can do it in vertex level. its 2-sat again. but i was not expection so easy solution. 2009/8/13 tvn <nguyenthanh...@gmail.com> > > Given a graph G where each vertex has a forbidden coloring (R,G,or B). > Constraint 3-Coloring problem asks if G is 3-colorable (such that the > forbidden constraint color is met). P or NP-Complete ? Prove it. > > > --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
