Carnegie Mellon University
Browse

Odd Hole Recognition in Graphs of Bounded Clique Size

Download (142.8 kB)
journal contribution
posted on 2009-10-01, 00:00 authored by Michele Conforti, Gerard CornuejolsGerard Cornuejols, Xinming Liu, Kristina Vušković, Giacomo Zambelli
In a graph G, an odd hole is an induced odd cycle of length at least five. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class Ck of graphs whose cliques have a size bounded by a constant k. Given a graph G in Ck, we show how to recognize in polynomial time whether G contains an odd hole.

History

Date

2009-10-01

Usage metrics

    Categories

    Keywords

    odd holerecognition algorithmcleaningdecompositionBusiness and Management not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC