Graph minors. XXI. graphs with unique linkages

DOI10.1016/j.jctb.2008.08.003zbMath1229.05253OpenAlexW2158421820MaRDI QIDQ1026001

Neil Robertson, P. D. Seymour

Publication date: 23 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.jctb.2008.08.003

zbMATH Keywords

tree-widthgraph minorsdisjoint pathsintertwining conjecture

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph minors (05C83)

Related Items

Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, The structure of graphs with a vital linkage of order 2, Planar disjoint-paths completion, Irrelevant vertices for the planar disjoint paths problem, Some recent progress and applications in graph minor theory, Effective computation of immersion obstructions for unions of graph classes, Adapting the Directed Grid Theorem into an FPT Algorithm, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Embedding graphs in the torus in linear time, Combing a Linkage in an Annulus, The disjoint paths problem in quadratic time, Graph minors. XXII. Irrelevant vertices in linkage problems, Packing topological minors half‐integrally, Confronting intractability via parameters, The size of an intertwine, Tight Bounds for Linkages in Planar Graphs, \(K_{6}\) minors in large 6-connected graphs, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Rigid linkages and partial zero forcing, Tree-width and planar minors, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, The Parameterized Complexity of Graph Cyclability, A lower bound on the tree-width of graphs with irrelevant vertices

Cites Work

• Graph minors. XX: Wagner's conjecture
• A Menger-like property of tree-width: The finite case
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XVII: Taming a vortex
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XII: Distance on a surface
• Curves von 2-manifolds and isotopies
• Dissections and Intertwinings of Graphs
• Unnamed Item