Structure theorem and isomorphism test for graphs with excluded topological subgraphs

DOI10.1145/2213977.2213996zbMath1286.05106arXiv1111.1109OpenAlexW2136923206MaRDI QIDQ5415474

Martin Grohe, Dániel Marx

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilitygraph isomorphismtopological minors

Mathematics Subject Classification ID

Trees (05C05) Graph minors (05C83) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (max. 100)

Characterising bounded expansion by neighbourhood complexity ⋮ The QAP-polytope and the graph isomorphism problem ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Graph isomorphism for graph classes characterized by two forbidden induced subgraphs ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Graphs with no 7-wheel subdivision ⋮ Lift-contractions ⋮ Graph isomorphism restricted by lists

This page was built for publication: Structure theorem and isomorphism test for graphs with excluded topological subgraphs