This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Padberg, M. Search for Related Content

Almost Perfect Matrices and Graphs

17, rue Vendome, 13007 Marseille, France
manfred{at}padberg.com

We introduce the notions of -projection and -projection that map almost integral polytopes associated with almost perfect graphs G with n nodes from ⁿ into ^n–, where is the maximum clique size in G. We show that C. Berge's strong perfect graph conjecture is correct if and only if the projection (of either kind) of such polytopes is again almost integral in ^n–. Several important properties of -projections and -projections are established. We prove, among other results, that the strong perfect graph conjecture is wrong if an -projection and a related -projection of an almost integral polytope with 2 (n–1)/2 produce different polytopes in ^n–.

Key Words: Perfect graphs; perfect zero-one matrices; strong perfect graph conjecture; orthogonal projections; polyhedra
History: Received: February 17, 1999; revision received: February 18, 2000;