Dynamic programming algorithm for NP-complete problem
[Edited ro reflect the intended meaning of the 3rd condition]

I believe you you describe the graph vertex coloration problem with a variation . We allow a vertex to have multiple colours : 


No adjacent nodes should be colored with the same color.
Every node should have at least one color.
For every pair of nodes (x,y) with x /neq y , one of these nodes must be colored with a color that the other is not colored with.


I want to present two situations, due to the nature of condition 3.

a) If only 1 and 2 apply. The minimum number of sets will be found if we color each node with only one color. Every other color applied to a node not only does not help solve the problem, but it adds additional constraints. Therefore this problem can be reduced to the single-colored vertex coloring problem.

b) 1,2 and 3 apply. For starters, let's 1-colour the graph. That give us a number of sets, let it be S1. For node belonging to different colours, the 3rd condition holds. However, for nodes belonging to the same colour, it doesn't. For every set, the problem of separating the same-set nodes reduces to colouring a full node graph, which we know needs N colours. However, we need not use new colours. We can re-use the already-used colours that of course obey the condition 1. 

Therefore, we can create a graph this way: Create a full graph containing all the nodes in the same set. Then, extend it with the nodes that are adjacent to the set colours. Maintain the existing colour for the added nodes (not belonging to the full graph). Also, add a node with the color of the set that is adjacent to every other node in the full graph, so that the original colour cannot be used. Then, try to colour the new graph. Repeat for every set (S1 repeats).

A sketch of the algorithm follows

Multi-colour(graph G) :


Color the graph with 1 color per node. Let S0 be the number of colors used.
For every color ( i from 1 to S0 ) : 

a. Create a full graph containing the nodes with THIS color.

b. Add to the graph the nodes adjacent to the nodes colored with THIS color. The adjacent nodes are colored with their colored from step 1.

c. Add a node adjacent to the nodes from step a. Color it with THIS color.

d. Color the graph. Prefer colors that were used in step 1. if none is eligible, use a NEW color.

e. Add every NEW color to the list of "used" colors. Let Si be the number of new colors used. (Si can be zero or positive ). S0 = S0 + Si . 
S0 is the number of minimum sets.


Complexity: The number of sets created by step 1 is O(n), where n is the number of vertices. Therefore this problem belongs in the same complexity as the graph coloring problem. 

My algorithm is a top-down approach, therefore it is not dynamic programming. I do not know if dynamic programming could be applied to this problem. Does the Principle of Optimality hold for this problem?