Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks (Q1964591)

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)}\).