Building counterexamples Original Research Article

A conjecture concerning perfect graphs asserts that if for a Berge graph G the following three conditions hold: (1) neither G, nor G has an even pair; (2) neither G, nor G has a stable cutset; (3) neither G, nor G has a star-cutset, then G or G is diamond-free. We show that this conjecture is not valid and that, in a way, every weaker version is false too. To this end, we construct a class of perfect graphs satisfying the hypothesis above and indicate counterexamples within this class for the instances of the conjecture obtained by replacing the diamond with any graph H which is the join of a clique and a stable set.