A 0,1 matrix A is near-perfect if the integer hull of the polyhedron {x≥0:Ax•n1} can be obtained by adding one extra (rank) constraint. The paper shows that in general, such matrices arise as the clique-node incidence matrices of graphs. It gives a colouring-like characterization of the corresponding class of near-perfect graphs which show that one need only check integrality of a certain linear program for each 0,1,2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0,1-valued objective functions. The paper also makes the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. It shows that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) The present results are used to strengthen (and give a new proof of) a theorem of Padberg. This result in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.
