Minimal imperfect graphs: A simple approach (Q1924490)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 936871
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Minimal imperfect graphs: A simple approach |
scientific article; zbMATH DE number 936871 |
Statements
Minimal imperfect graphs: A simple approach (English)
0 references
11 March 1997
0 references
For a graph \(G\), let \(\omega(G)\) denote the cardinality of a maximum clique of \(G\), and \(\alpha(G)\) the cardinality of a maximum independent set. \textit{L. Lovász} [J. Comb. Theory, Ser. B 13, 95-98 (1972; Zbl 0241.05107)] showed that a graph \(G\) is perfect iff \(|H|\leq \omega(H)\alpha(H)\) for every induced subgraph \(H\) of \(G\). This paper provides a short proof of this theorem, and discusses its consequences.
0 references
perfect graphs
0 references
clique
0 references
independent set
0 references
0.8191680312156677
0 references
0.805155336856842
0 references
0.803234338760376
0 references
0.8006922006607056
0 references
