Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/919407
- Well-quasi-orders in subclasses of bounded treewidth graphs
Fellows, Michael R.;
Rosamond, Frances A.
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- 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 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. Our results give an algorithm for recognizing any graph family in these classes which is closed under the corresponding minor order refinement.
- 4th International Workshop, Parameterized and Exact Computation (IWPEC 2009). Parameterized and Exact Computation 4th International Workshop, IWPEC 2009: Revised Selected Papers (Copenhagen, Denmark 10-11 September, 2009) p. 149-160
- Publisher Link
- Springer Berlin
bounded treewidth graphs;
- Resource Type
- conference paper