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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
* Currently this author is a Clay Mathematics Institute Research Fellow.
** Supported by NSF grant DMI-0352885 and ONR grant N00014-97-1-0196.
† Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912.
‡ Supported by EPSRC grant GR/R35629/01.
Rights and permissions
About this article
Cite this article
Chudnovsky*, M., Cornuéjols**, G., Liu†, X. et al. Recognizing Berge Graphs. Combinatorica 25, 143–186 (2005). https://doi.org/10.1007/s00493-005-0012-8
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00493-005-0012-8