Isomorphism Testing for Graphs Excluding Small Minors

DOI10.1137/21M1401930MaRDI QIDQ5885601zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Daniel Neuen, Daniel Wiebking

Publication date 4 April 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.07671

zbMATH Keywords

excluded minorsgraph isomorphism problemstructure of automorphism group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• An improved isomorphism test for bounded-tree-width graphs
• An improved isomorphism test for bounded-tree-width graphs

Cites work

• A unifying method for the design of algorithms canonizing combinatorial objects
• An extremal function for contractions of graphs
• An improved isomorphism test for bounded-tree-width graphs
• An optimal lower bound on the number of variables for graph identification
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph minors. XVI: Excluding a non-planar graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 7221274 (Why is no real title available?)
• scientific article; zbMATH DE number 3732083 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 3815 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Hypergraph Isomorphism for Groups with Restricted Composition Factors
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Lower bound of the Hadwiger number of graphs by their average degree
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the orders of primitive groups with restricted nonabelian composition factors
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The isomorphism problem for classes of graphs closed under contraction
• Tight lower and upper bounds for the complexity of canonical colour refinement

Cited in

(10)

• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• A proof system for graph (non)-isomorphism verification
• Hypergraph Isomorphism for Groups with Restricted Composition Factors
• Isomorphism Testing Parameterized by Genus and Beyond
• Faster isomorphism for p-groups of class 2 and exponent p
• Isomorphism testing for graphs excluding small topological subgraphs
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• Isomorphism testing for graphs excluding small topological subgraphs

This page was built for publication: Isomorphism Testing for Graphs Excluding Small Minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885601)