Isomorphism of graphs of bounded valence can be tested in polynomial time

Abstract

Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the subgroup of G which stabilizes the color classes. Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections. The algorithm for the latter problem involves several divide-and-conquer tricks. The problem is solved sequentially on the G-orbits. An orbit is broken into a minimal set of blocks permuted by G. The hypothesis on G guarantees the existence of a 'large' subgroup P which acts as a p-group on the blocks. A similar process is repeated for each coset of P on G. Some results on primitive permutation groups are used to show that the algorithm runs in polynomial time.