This note investigates the boundary between polynomially-solvable Max Cut and NP Hard Max Cut instances when they are classified only on the basis of the sign pattern of the objective function coefficients, i.e., of the orthant containing the objective function vector. It turns out that the...

The cut polyhedron cut(G) of an undirected graph G = (V, E) is the dominant of the convex hull of all of its nonempty edge cutsets. After examining various compact extended formulations for cut(G), we study some of its polyhedral properties. In particular, we characterize all of the facets...