Minimal imperfect graphs: A simple approach

DOI10.1007/BF01844846MaRDI QIDQ1924490zbMATH OpenFDO

Authors G. S. Gasparian

Publication date 11 March 1997

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01844846

zbMATH Keywords

cliqueindependent setperfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

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.

Recommendations

• A note on perfect graphs
• Nikolai Ivanovich Lobachevskii (on the bicentenary of his birth)
• Progress on perfect graphs
• Perfect graphs
• Sum-perfect graphs

Cites work

• A characterization of perfect graphs
• Graphical properties related to minimal imperfection
• scientific article; zbMATH DE number 3332248 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• On certain polytopes associated with graphs
• Perfect zero–one matrices

Cited in

(14)

• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• No antitwins in minimal imperfect graphs
• Non-regular square bipartite designs
• Perfection thickness of graphs
• Point partition numbers: perfect graphs
• Some aspects of minimal imperfect graphs
• Nikolai Ivanovich Lobachevskii (on the bicentenary of his birth)
• A short proof of the wonderful lemma
• On ideal clutters, metrics and multiflows
• Graph Imperfection with a Co-Site Constraint
• Attempting perfect hypergraphs
• Problems and results on 1-cross-intersecting set pair systems
• A Sum of Squares Characterization of Perfect Graphs
• -boundedness and related problems on graphs without long induced paths: a survey

This page was built for publication: Minimal imperfect graphs: A simple approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924490)