Minimum cardinality graph partition that removes specific edges I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for an algorithm.
Input: A connected, undirected graph G = (V, E) in which certain edges are labelled &quot;bad&quot;.
Output: The minimum cardinality partition of V such that 1) all of the induced subgraphs of the partition are connected, and 2) none of the induced subgraphs contains a bad edge.
Thanks!
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.)