Almost perfect matrices and graphs

Almost perfect matrices and graphs

0.00 Avg rating0 Votes
Article ID: iaor20041134
Country: United States
Volume: 26
Issue: 1
Start Page Number: 1
End Page Number: 18
Publication Date: Feb 2001
Journal: Mathematics of Operations Research
Authors:
Keywords: matrices
Abstract:

We introduce the notions of ω-projection and κ-projection that map almost integral polytopes associated with almost perfect graphs G with n nodes from n 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 are established. We prove, among other results, that the strong perfect graph conjecture is wrong if an ω-projection and related κ-projection of an almost integral polytope with 2 ≤ ω ≤ (n − 1)/2 produce different polytopes in n−ω.

Reviews

Required fields are marked *. Your email address will not be published.