Max-cut is simply a division of the vertices of an arbitrary
graph into two subsets, such that the number of edges going
from vertices in one subset to vertices in the other subset
is maximized. From Garey and Johnson, max-cut is NP-complete.
Note that max-cut is different from max bisection in that max cut does not require the subsets to have equal size. However, both problems are NP-complete.