Carnegie Mellon University
Browse
Even-Hole-Free Graphs Part I: Decomposition Theorem.pdf.pdf' (427.34 kB)

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

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC