Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
From MaRDI portal
Publication:5252660
DOI10.1137/120892234zbMath1314.05134OpenAlexW2037713618MaRDI QIDQ5252660
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/120892234
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (26)
Isomorphism Testing for Graphs Excluding Small Minors ⋮ Excluding subdivisions of bounded degree graphs ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Minors and dimension ⋮ An improved isomorphism test for bounded-tree-width graphs ⋮ Layered separators in minor-closed graph classes with applications ⋮ A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three ⋮ Order Reconfiguration under Width Constraints ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ Packing topological minors half‐integrally ⋮ Long induced paths in minor-closed graph classes and beyond ⋮ A Faster Isomorphism Test for Graphs of Small Degree ⋮ Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Improved Bounds for Centered Colorings ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Unnamed Item ⋮ A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors ⋮ Computing with Tangles ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ A Structure Theorem for Strong Immersions ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ Canonisation and Definability for Graphs of Bounded Rank Width
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Implicit branching and parameterized partial cover problems
- Graph minors. XX: Wagner's conjecture
- Parameterized graph separation problems
- Some recent progress and applications in graph minor theory
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XIII: The disjoint paths problem
- Local tree-width, excluded minors, and approximation algorithms
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- A shorter proof of the graph minor algorithm
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Edge-disjoint paths in Planar graphs with constant congestion
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
- Divide-and-Color
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- Fixed-point definability and polynomial time on graphs with excluded minors
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- A simpler algorithm and shorter proof for the graph minor decomposition
- Finding topological subgraphs is fixed-parameter tractable
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
This page was built for publication: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
