Carnegie Mellon University
Browse

Decomposing Berge Graphs Containing No Proper Wheel, Long Prism Or Their Complements

Download (3.14 MB)
journal contribution
posted on 1981-10-01, 00:00 authored by Michele Conforti, Gerard CornuejolsGerard Cornuejols, Giacomo Zambelli
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.

History

Date

1981-10-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC