The strong perfect graph conjecture for pan-free graphs (Q1112848)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The strong perfect graph conjecture for pan-free graphs
scientific article

    Statements

    The strong perfect graph conjecture for pan-free graphs (English)
    0 references
    0 references
    1989
    0 references
    A graph \(G\) is perfect if for every induced subgraph \(F\) of \(G\), the chromatic number \(\chi(F)\) equals the largest number \(\omega(F)\) of pairwise adjacent vertices in \(F\). Berge's famous Strong perfect graph conjecture asserts that a graph \(G\) is perfect if and only if neither \(G\) nor its complement \(\overline{G}\) contains an odd chordless cycle of length at least five. Its resolution has eluded researchers for more than twenty years. We prove that the conjecture is true for a class of graphs which strictly contains the claw-free graphs.
    0 references
    0 references
    clique number
    0 references
    chromatic number
    0 references
    Strong perfect graph conjecture
    0 references
    claw-free graphs
    0 references
    0 references