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
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
clique number
0 references
chromatic number
0 references
Strong perfect graph conjecture
0 references
claw-free graphs
0 references