Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks

DOI10.1007/S004930050059MaRDI QIDQ1964591zbMATH OpenOpenAlexFDO

Authors S. A. Evdokimov, Ilya Ponomarenko

Publication date 21 February 2000

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930050059

zbMATH Keywords

coloured graphsJordan blocks

Mathematics Subject Classification ID

Other designs, configurations (05B30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The complexity of the graph isomorphism problem is unknown: for general graphs with \(n\) vertices the best known upper bound is \(n^{O(\sqrt{n/\log n})}\). If the multiplicities of the eigenvalues of the graph are bounded by \(k\), an algorithm of complexity \(n^{O(k)}\) is known. This is now reduced to \(c_k n^{O(1)}\).

Recommendations

• On the isomorphism of graphs having some eigenvalues of moderate multiplicity
• On testing isomorphism of graphs of bounded eigenvalue multiplicity
• Graph algebras and the graph isomorphism problem
• scientific article; zbMATH DE number 2086379
• scientific article; zbMATH DE number 3815

Cited in

(15)

• Permutation group approach to association schemes
• Graph algebras and the graph isomorphism problem
• On the geometric graph isomorphism problem
• Two inequalities for parameters of a cellular algebra
• Colored hypergraph isomorphism is fixed parameter tractable
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• Graph isomorphism parameterized by elimination distance to bounded degree
• On testing isomorphism of graphs of bounded eigenvalue multiplicity
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• scientific article; zbMATH DE number 3815 (Why is no real title available?)
• scientific article; zbMATH DE number 2086379 (Why is no real title available?)
• scientific article; zbMATH DE number 910921 (Why is no real title available?)
• Graph isomorphism restricted by lists
• Isomorphism testing of k-spanning tournaments is fixed parameter tractable
• On the isomorphism of graphs having some eigenvalues of moderate multiplicity

This page was built for publication: Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks

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