Carnegie Mellon University
Browse

Even-Hole-Free Graphs Part I: Decomposition Theorem

Download (427.34 kB)
journal contribution
posted on 1969-03-01, 00:00 authored by Michele Conforti, Gerard CornuejolsGerard Cornuejols, Ajai Kapoor, Kristina Vušković
We prove a decomposition theorem for even-hole-free graphs. The decompositions used are 2-joins and star, double-star and triple-star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even-hole-free graphs.

History

Date

1969-03-01

Usage metrics

    Categories

    Keywords

    even-hole-free graphs; decomposition theorem; double-star cutset; 2-join; blocking sequenceBusiness and Management not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC