Approximate max k-cut with subgraph guarantee