Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs

Danny Hermelin (MPI Saarbruecken)

In this talk I will show that three subclasses of bounded treewidth graphs are well-quasi-ordered by refinements of the minor order. Specifically, I will show that graphs with bounded feedback-vertex-set are well-quasi-ordered by the topological-minor order, graphs with bounded vertex-covers are well-quasi-ordered by the subgraph order, and graphs with bounded circumference are well-quasi-ordered by the induced-minor order. These results give an algorithm for recognizing any graph family in these classes which is closed under the corresponding minor order refinement.

back to EIDMA Seminar Combinatorial Theory announcements