Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/919407

OpenURL Link
Title
Well-quasi-orders in subclasses of bounded treewidth graphs
Author/Creator
Fellows, Michael R.;  Hermelin, Danny;  Rosamond, Frances A.
Institution
The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
Description
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.
Relation
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
http://dx.doi.org/10.1007/978-3-642-11269-0_12
Date
2009
Publisher
Springer Berlin
Keyword(s)
bounded treewidth graphs;  bounded feedback-vertex-set;  well-quasi-orders
Resource Type
conference paper
Identifier
http://hdl.handle.net/1959.13/919407
Identifier
ISBN:9783642112683
Reviewed
Reviewed
25 Visitors 28 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Well-quasi-orders in subclasses of bounded treewidth graphs"
 
OR