Minimal imperfect graphs: A simple approach
type: Item
instance of: scholarly article
title: Minimal imperfect graphs: A simple approach
zbMATH Open document ID: 0858.05044
DOI: 10.1007/BF01844846
author: G. S. Gasparian
published in: Combinatorica
publication date: 1997-03-11T00:00:00Z
review text: 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.
reviewed by: Chris Jagger
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 936871
zbMATH Keywords: perfect graphs
zbMATH Keywords: clique
zbMATH Keywords: independent set
MaRDI profile type: Publication
cites work: Graphical properties related to minimal imperfection
cites work: On certain polytopes associated with graphs
cites work: Q5609153
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: A characterization of perfect graphs
cites work: Perfect zero–one matrices
description: scientific article; zbMATH DE number 936871