Graph minors. X. Obstructions to tree-decomposition

1991/07/01 by Neil Robertson, Paul Seymour, P.D Seymour · 435 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary tree #Combinatorics #Computer science #Discrete mathematics #Gomory–Hu tree #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #K-ary tree #Line graph #Mathematics #Pathwidth #Tree (set theory) #Tree decomposition #Tree structure

paper · doi:10.1016/0095-8956(91)90061-n

published in Journal of Combinatorial Theory, Series B 52(2), 153-190 (Elsevier BV)

crossref issued 1991/07/01 · crossref published 1991/07/01 · crossref published-print 1991/07/01 · openalex publication_date 1991/07/01 · crossref created 2005/02/09 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/06/29 · openalex updated_date 2026/08/08

Citations

• Graph minors. V. Excluding a planar graph

Cited by

• Approximating clique-width and branch-width
• Testing branch-width
• On the excluded minors for the matroids of branch-width k
• The branchwidth of graphs and their cycle matroids
• Matroid tree-width
• Computing branchwidth via efficient triangulations and blocks
• Finding Branch-Decompositions and Rank-Decompositions
• Approximating rank-width and clique-width quickly
• Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
• Tour Merging via Branch-Decomposition
• Fast FPT-approximation of branchwidth
• Rank-width and vertex-minors
• Clique Cover on Sparse Networks
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• New upper bounds on the decomposability of planar graphs
• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
• Graph Minors
• Some Recent Progress and Applications in Graph Minor Theory
• Graph Minors
• Graph Minors .XIV. Extending an Embedding
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph Minors. XXII. Irrelevant vertices in linkage problems
• Graph Minors. XIX. Well-quasi-ordering on a surface
• Graph minors. XXI. Graphs with unique linkages
• Graph Minors. XVIII. Tree-decompositions and well-quasi-ordering
• Branch-decomposition [wikipedia]
• Graph structure theorem [wikipedia]