Recognizing Berge Graphs Maria Chudnovsky Gerard Cornuejols Xinming Liu Paul Seymour Kristina Vušcović 10.1184/R1/6707654.v1 https://kilthub.cmu.edu/articles/journal_contribution/Recognizing_Berge_Graphs/6707654 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)|<sup>9</sup>). This is independent of the recent proof of the strong perfect graph conjecture. 1991-01-01 00:00:00 Business Management