Split-neighbourhood graphs and the strong perfect graph conjecture (Q1892848)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Split-neighbourhood graphs and the strong perfect graph conjecture |
scientific article |
Statements
Split-neighbourhood graphs and the strong perfect graph conjecture (English)
0 references
2 July 1995
0 references
We introduce the class of graphs such that every induced subgraph possesses a vertex whose neighbourhood can be split into a clique and a stable set. We prove that this class satisfies Berge's strong perfect graph conjecture. This class contains several well-known classes of (perfect) graphs and is polynomially recognizable.
0 references
chromatic number
0 references
perfect graph
0 references
split-neighbourhood
0 references
clique
0 references
stable set
0 references
Berge's strong perfect graph conjecture
0 references
polynomially recognizable
0 references
