Name of this graph partitioning problem? (related to coloring)
(Copied from a comment:)
If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as &quot;maximum k-cut&quot; and also &quot;maximum k-colorable subgraph&quot;.