Building counterexamples
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\)).
- A characterization of perfect graphs
- A new property of critical imperfect graphs and some consequences
- A semi-strong perfect graph theorem
- Coloring graphs with stable cutsets
- Coloring perfect \((K_ 4\)-e)-free graphs
- Compositions for perfect graphs
- Counterexamples to three conjectures concerning perfect graphs
- Star-cutsets and perfect graphs
- Two-colourings that decompose perfect graphs
This page was built for publication: Building counterexamples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363703)
