Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?
For example, in the following picture there is a graph with v1, v7, v8, v9 labeled with 0 and the rest of the vertices labeled with 1. We can either remove v1 and will have 3 vertices labeled with 0 and 5 vertices labeled with 1, thus the size of the smallest group being 3. Or we can remove v4, v3 and v2, then we will have 4 vertices labelled with 0 and 2 vertices labelled with 1, thus the size of the smallest group being 2. We can remove isolated vertices too, but it will either decrease or wont change the size of the smallest group, so this isn't useful. Overall number of vertices removed is of no interest, it's just the size of the smallest group.