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