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. |