Recognizing Berge graphs. (English) Zbl 1089.05027
A graph \(G\) is Berge if no induced subgraph of \(G\) and its complement \(\overline{G}\) is an odd cycle of length at least five. It has been an open question whether testing Bergeness of a graph belongs to NP. In the present paper the authors give an algorithm for testing Bergeness with running time \(O(|V(G)|^9)\). It makes use of a “cleaning” technique which generates polynomially many subsets such that one is a near-cleaner for a shortest odd hole.
The algorithm given here is independent of the proof of Berge’s strong graph conjecture.
The algorithm given here is independent of the proof of Berge’s strong graph conjecture.
Reviewer: Ulrike Baumann (Dresden)
MSC:
05C17 | Perfect graphs |