Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications (Q1759678): Difference between revisions

Certain partial orders on graphs become well quasi orders when restricted to certain classes of graphs. Here the partial orders refine minors, defined by vertex deletion, edge deletion, edge contraction or topological contraction. Parameters such as treewidth, vertex cover number or circumference define the classes considered. Two sophisticated tools are used to show that graphs of bounded vertex cover are well quasi ordered by induced subgraphs, graphs of bounded feedback vertex set are well quasi ordered by the topological minors, and graphs of bounded circumference are well quasi ordered by the induced minors. These well quasi orderings enable fixed parameter algorithms (the bound on the graph parameter is fixed) recognizing graph families in these classes which are closed under the corresponding order. A conference version appeared in [Proceedings of IWPEC 2009, Lect.\ Notes Comput.\ 5917, 149--160 (2009; Zbl 1264.68120)].