Forbidden minors characterization of partial 3-trees
From MaRDI portal
Publication:913807
DOI10.1016/0012-365X(90)90292-PzbMath0701.05016MaRDI QIDQ913807
Andrzej Proskurowski, Stefan Arnborg, Derek Gordon Corneil
Publication date: 1990
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (51)
The structure of obstructions to treewidth and pathwidth ⋮ On the critical densities of minor-closed classes ⋮ Seeing Arboretum for the (partial k-) Trees ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Treewidth distance on phylogenetic trees ⋮ Characterizing width two for variants of treewidth ⋮ Simplicial decompositions of graphs: A survey of applications ⋮ Constructive linear time algorithms for branchwidth ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ Sparse obstructions for minor-covering parameters ⋮ Forbidding Kuratowski Graphs as Immersions ⋮ Gallai's conjecture for graphs with treewidth 3 ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ Bounding tree-width via contraction on the projective plane and torus ⋮ Characterising graphs with no subdivision of a wheel of bounded diameter ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ All longest cycles in a 2‐connected partial 3‐tree share a common vertex ⋮ Packing Signatures in Signed Graphs ⋮ Connected search for a lazy robber ⋮ Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings ⋮ Tangle bases: Revisited ⋮ Mineurs d'arbres avec racines ⋮ On strict brambles ⋮ A lower bound for treewidth and its consequences ⋮ Unnamed Item ⋮ Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees ⋮ On two dual classes of planar graphs ⋮ On 3-cutwidth critical graphs ⋮ Unnamed Item ⋮ Three-connected graphs whose maximum nullity is at most three ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Forbidden directed minors and Kelly-width ⋮ A characterization of some graph classes using excluded minors ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ A new graph parameter related to bounded rank positive semidefinite matrix completions ⋮ Recognizing digraphs of Kelly-width 2 ⋮ Treewidth, crushing and hyperbolic volume ⋮ Minor obstructions for apex-pseudoforests ⋮ Transversals of longest paths ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Structure and recognition of graphs with no 6-wheel subdivision ⋮ On the treewidth of Hanoi graphs ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ A note on partial 3-trees and homomorphism bases of graphs ⋮ Minors of quasi 4-connected graphs ⋮ Minimal acyclic forbidden minors for the family of graphs with bounded path-width
Cites Work
- Unnamed Item
- Unnamed Item
- Separating subgraphs in k-trees: Cables and caterpillars
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Steiner trees, partial 2–trees, and minimum IFI networks
- Disjoint Paths—A Survey
- Characterization and Recognition of Partial 3-Trees
- Complexity of Finding Embeddings in a k-Tree
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
- Networks immune to isolated failures
- Networks immune to isolated line failures
This page was built for publication: Forbidden minors characterization of partial 3-trees
