A Class of Facet Producing Graphs for Vertex Packing Polyhedra.

摘要

The author examines a family F of regular graphs which properly generalizes cliques,holes and anti-holes. A characterization is given for members of F whose associated vertex packing polytope contains a facet which cannot be derived from any proper induced subgraph. Simple necessary and sufficient conditions are given for a graph in F to contain another as an induced subgraph;these conditions are used to show that the graphs in F satisfy the Strong Perfect Graph Conjecture. Complements of members of F are also studied and we show that if both a graph and its complement belong to F,then the graph is an odd hole or odd anti-hole. (Author)