Building counterexamples (Q1363703): Difference between revisions

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\)).