Recognizing Berge Graphs
journal contributionposted on 01.01.1991 by Maria Chudnovsky, Gerard Cornuejols, Xinming Liu, Paul Seymour, Kristina Vušcović
Any type of content formally published in an academic journal, usually following a peer-review process.
A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|9). This is independent of the recent proof of the strong perfect graph conjecture.