Decomposing berge graphs containing no proper wheels, long prisms or their complements

Conforti, Michele; Cornuéjols, Gérard; and Zambelli, Giacomo (2006) Decomposing berge graphs containing no proper wheels, long prisms or their complements Combinatorica, 26 (5). pp. 533-558. ISSN 0209-9683
Copy

In this paper we show that, if G is a Berge graph such that neither G nor its complement Ḡ contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph( a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect.

Full text not available from this repository.

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads