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
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
