Recognizing Berge graphs (Q2494439): Difference between revisions

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.