Building counterexamples
type: Item
instance of: scholarly article
title: Building counterexamples
zbMATH Open document ID: 0874.05024
DOI: 10.1016/S0012-365X(96)00081-7
author: Irena Rusu
published in: Discrete Mathematics
publication date: 1997-10-22T00:00:00Z
review text: A conjecture concerning perfect graphs asserts that if for a Berge graph \(G\) (i.e., a graph without odd holes and odd antiholes) the following three conditions hold: (1) neither \(G\), nor \(\overline {G}\) has an even pair; (2) neither \(G\), nor \(\overline {G}\) has a stable cutset; (3) neither \(G\), nor \(\overline {G}\) has a star-cutset, then \(G\) or \(\overline {G}\) is diamond-free. Since the diamond-free Berge graphs are perfect [see \textit{A. Tucker}, J. Comb. Theory, Ser. B 42, 313-318 (1987; Zbl 0585.05007)], a proof of this conjecture would also be a proof of the strong perfect graph conjecture. This paper gives a counterexample not only for this conjecture, but also for every weaker version of it obtained by replacing the diamond (\(K_{4}-e\)) with any graph \(H\) which is the join of a clique and a stable set (that is, all possible edges between the two sets are present in \(H\)).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1047090
zbMATH Keywords: perfect graph
zbMATH Keywords: even pair
zbMATH Keywords: stable cutset
zbMATH Keywords: diamond-free
zbMATH Keywords: minimal imperfect graph
Wikidata QID: Q56430121
MaRDI profile type: Publication
cites work: Star-cutsets and perfect graphs
cites work: Two-colourings that decompose perfect graphs
cites work: Compositions for perfect graphs
cites work: Counterexamples to three conjectures concerning perfect graphs
cites work: A characterization of perfect graphs
cites work: A new property of critical imperfect graphs and some consequences
cites work: A semi-strong perfect graph theorem
cites work: Coloring graphs with stable cutsets
cites work: Coloring perfect \((K_ 4\)-e)-free graphs
DBLP publication ID: journals/dm/Rusu97
description: scientific article; zbMATH DE number 1047090