Graph minors. X: Obstructions to tree-decomposition

DOI10.1016/0095-8956(91)90061-NzbMath0764.05069WikidataQ56001805 ScholiaQ56001805MaRDI QIDQ1179473

Neil Robertson, P. D. Seymour

Publication date: 26 June 1992

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

hypergraphs; separation; minors; tangle; tree-width; tree-decomposition

Mathematics Subject Classification ID

05C05: Trees

05C65: Hypergraphs

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05B35: Combinatorial aspects of matroids and geometric lattices

Related Items

A simple linear-time algorithm for finding path-decompositions of small width, Graph minors. XX: Wagner's conjecture, Quickly excluding a forest, The vertex separation number of a graph equals its path-width, A partial k-arboretum of graphs with bounded treewidth, Highly connected sets and the excluded grid theorem, Call routing and the ratcatcher, On the contractibility of a digraph onto \(K_ 4^*\), Improved self-reduction algorithms for graphs with bounded treewidth, On well quasiordering of finite languages, On the excluded minors for the matroids of branch-width \(k\), On the monotonicity of games generated by symmetric submodular functions., Graph minors. XVI: Excluding a non-planar graph, Graph minors. XVIII: Tree-decompositions and well-quasi-ordering, Clique-width of countable graphs: A compactness property., Graph minors. XIX: Well-quasi-ordering on a surface., Graph minors. XVII: Taming a vortex, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Computing the branchwidth of interval graphs, Strong branchwidth and local transversals, On the domination search number, Branch-width and well-quasi-ordering in matroids and graphs., On matroids of branch-width three., Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Fork-decompositions of matroids, Kernels in planar digraphs

Cites Work

• Unnamed Item
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XII: Distance on a surface
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen