Cut dominants and forbidden minors

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef [Math. Program, 53 (1992), pp. 147- 172]. We show how to derive each of the results from the other. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2.SCOPUS: ar.j