Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications

Michael Fellows, Danny Hermelin, Frances Rosamond

    Research output: Contribution to journalArticle

    Abstract

    We show that three subclasses of bounded treewidth graphs are well quasi ordered by refinements of the minor order. Specifically, we prove that graphs with bounded vertex cover are well quasi ordered by the induced subgraph order, graphs with bounded feedback vertex set are well quasi ordered by the topological-minor order, and graphs with bounded circumference are well quasi ordered by the induced minor order. Our results give algorithms for recognizing any graph family in these classes which is closed under the corresponding minor order refinement.
    Original languageEnglish
    Pages (from-to)3-18
    Number of pages16
    JournalAlgorithmica
    Volume64
    Issue number1
    DOIs
    Publication statusPublished - 2012

    Fingerprint Dive into the research topics of 'Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications'. Together they form a unique fingerprint.

    Cite this