Minimum cardinality graph partition that removes specific edges
Try to look at what happens when all the edges are bad edges.
What would the question be if I asked:

Can you partition the graph into three partitions, e.g. red, green, blue, such that for every edge, the &quot;color&quot; of the endpoints of each edge is &quot;chromatic&quot;.

(Let's also make the graph into a complete graph by adding &quot;good&quot; edges between every non-adjacent vertices.)