Forbidden minors to graphs with small feedback sets Original Research Article

Finite obstruction set characterizations for lower ideals in the minor order are guaranteed to exist by the graph minor theorem. In this paper we characterize several families of graphs with small feedback sets, namely k1-FEEDBACK VERTEX SET, k2-Feedback EDGE SET and (k1,k2)-FEEDBACK VERTEX/EDGE SET, for small integer parameters k1 and k2. Our constructive methods can compute obstruction sets for any minor-closed family of graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.