Forbidden minors to graphs with small feedback sets

DOI10.1016/S0012-365X(00)00083-2MaRDI QIDQ5931421zbMATH OpenDBLPWikidataFDO

Authors Michael J. Dinneen, Kevin Cattell, Michael R. Fellows

Publication date 8 July 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(00)00083-2

zbMATH Keywords

constructive methodfeedback setsgraph minor

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83)

Review text

Finite obstruction set characterizations for lower ideals in the minor order are guaranteed to exist by the graph minor theorem. In this paper, the authors characterize several families of graphs with small feedback sets. Their constructive methods can compute obstruction sets for any minor-closed family of graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.

Recommendations

• scientific article; zbMATH DE number 4144031
• scientific article; zbMATH DE number 3961651
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• On the geometry of graphs with a forbidden minor
• Forbidden minors for the class of graphs G with (G) 2
• Clique minors in graphs with a forbidden subgraph
• Minimal forbidden subgraphs of reducible graph properties
• Minimal separators in graph classes defined by small forbidden induced subgraphs
• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs

Cited in

(22)

• On computing graph minor obstruction sets
• Minor obstructions for apex-pseudoforests
• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
• Sparse obstructions for minor-covering parameters
• Properties of vertex cover obstructions
• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
• Outerplanar obstructions for the feedback vertex set
• On characterizations by nice forbidding sets
• Outerplanar obstructions for a feedback vertex set
• scientific article; zbMATH DE number 1543064 (Why is no real title available?)
• scientific article; zbMATH DE number 1543076 (Why is no real title available?)
• The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed
• Confronting intractability via parameters
• scientific article; zbMATH DE number 10087 (Why is no real title available?)
• Forbidden minors for graphs with no first obstruction to parametric Feynman integration
• Forbidden directed minors and Kelly-width
• Obstructions to within a few vertices or edges of acyclic
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Minor-obstructions for apex sub-unicyclic graphs
• Graph parameters, universal obstructions, and WQO
• An overview of universal obstructions for graph parameters
• Minor-obstructions for apex sub-unicyclic graphs

This page was built for publication: Forbidden minors to graphs with small feedback sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5931421)