Preperfect graphs (Q684406)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Preperfect graphs |
scientific article |
Statements
Preperfect graphs (English)
0 references
15 September 1993
0 references
A vertex \(x\) is said to be predominant if there exists another vertex \(y\) of \(G\) such that either every maximum clique of \(G\) containing \(y\) contains \(x\) or every maximum stable set containing \(x\) contains \(y\). A graph is then called preperfect if every induced subgraph has a predominant vertex. This paper shows that preperfect graphs are perfect and that several well-known kinds of perfect graphs are preperfect. Meanwhile, it is also shown that a graph \(G\) is perfect iff every induced subgraph \(H\) of \(G\) possesses a minimal absorbant set that meets all maximum cliques of \(H\).
0 references
predominant
0 references
clique
0 references
stable set
0 references
preperfect graphs
0 references
perfect graphs
0 references