Well-quasi-orders in subclasses of bounded treewidth graphs

Title: Well-quasi-orders in subclasses of bounded treewidth graphs
Creator: Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances A.
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
Publisher: Springer Berlin
Resource Type: conference paper
Date: 2009
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.
Subject: bounded treewidth graphs; bounded feedback-vertex-set; well-quasi-orders
Identifier: uon:8865
Identifier: http://hdl.handle.net/1959.13/919407
Identifier: ISBN:9783642112683
Reviewed

		Thumbnail	File	Description	Size	Format