Minimal acyclic forbidden minors for the family of graphs with bounded path-width

DOI10.1016/0012-365X(94)90092-2zbMath0795.05123OpenAlexW2026646714MaRDI QIDQ1322236

Atsushi Takahashi, Yoji Kajitani, Shuichi Ueno

Publication date: 5 May 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)90092-2

zbMATH Keywords

forbidden minorspath-width

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Related Items (33)

Contraction obstructions for connected graph searching ⋮ Graph Minors and Parameterized Algorithm Design ⋮ On the Wiener index, distance cospectrality and transmission-regular graphs ⋮ On the pathwidth of hyperbolic 3-manifolds ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Sparse obstructions for minor-covering parameters ⋮ Forbidding Kuratowski Graphs as Immersions ⋮ Outerplanar obstructions for matroid pathwidth ⋮ Outerplanar obstructions for a feedback vertex set ⋮ Forbidden graphs for tree-depth ⋮ On Evasion Games on Graphs ⋮ Graph Searching in a Crime Wave ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph ⋮ Characterizing graphs of small carving-width ⋮ Cutwidth: obstructions and algorithmic aspects ⋮ Mixed searching and proper-path-width ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph ⋮ Connected graph searching ⋮ Unnamed Item ⋮ On the number of labeled graphs of bounded treewidth ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ FPT is characterized by useful obstruction sets ⋮ Nondeterministic operations on finite relational structures ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ Outerplanar Obstructions for the Feedback Vertex Set ⋮ Obstructions for Tree-depth ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Linear rank-width and linear clique-width of trees ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Bemerkungen zu Hadwigers Vermutung
• Separating subgraphs in k-trees: Cables and caterpillars
• Forbidden minors characterization of partial 3-trees
• Graph minors. I. Excluding a forest
• Graph minors. VI. Disjoint paths across a disc
• 103 graphs that are irreducible for the projective plane
• Complexity of Finding Embeddings in a k-Tree
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal acyclic forbidden minors for the family of graphs with bounded path-width