A 0-1 matrix A is ideal if the polyhedron Q(A)=conv{x∈Q’V:Aëx∈1, x∈0∈ (V denotes the column index set of A) is integral. Similarly a matrix is perfect if P(A)=conv{x∈Q’V:Aëx∈1,x∈0∈ is integral. Little is known about the relationship between these two classes of matrices. The paper considers a transformation between the two classes which enables it to apply Lehman’s modified theorem about deletion-minimal nonideal matrices to obtain new results about packing polyhedra. This results in a polyhedral description for the stable set polytopes of near-bipartite graphs (the deletion of any neighbourhood produces a bipartite graph). Note that this class includes the complements of line graphs. To date, this is the only natural class, besides the perfect graphs, for which such a description is known for the graphs and their complements. Some remarks are also made on possible approaches to describing the stable set polyhedra of quasi-line graphs, and more generally claw-free graphs. These results also yield a new class of t-perfect graphs.
