Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-11269-0_12 | IWPEC |
Keywords | Field | DocType |
bounded treewidth graph,induced-minor order,graph family,subgraph order,bounded feedback-vertex-set,topological-minor order,corresponding minor order refinement,bounded vertex-covers,bounded treewidth graphs,bounded circumference,minor order,vertex cover,feedback vertex set | Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Partial k-tree,Chordal graph,Clique-sum,Treewidth,Pathwidth,1-planar graph,Mathematics | Conference |
Volume | ISSN | Citations |
5917 | 0302-9743 | 6 |
PageRank | References | Authors |
0.47 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Danny Hermelin | 2 | 790 | 48.62 |
| Frances A. Rosamond | 3 | 304 | 15.94 |