Carnegie Mellon University
Browse
Recognizing Berge Graphs.pdf.pdf' (259.84 kB)

Recognizing Berge Graphs

Download (259.84 kB)
journal contribution
posted on 1991-01-01, 00:00 authored by Maria Chudnovsky, Gerard CornuejolsGerard Cornuejols, Xinming Liu, Paul Seymour, Kristina Vušcović
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.

History

Date

1991-01-01

Usage metrics

    Categories

    Keywords

    BusinessManagement

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC