Abstract
Johannes Köbler and Jacobo Torán
Abstract:
We prove that the graph isomorphism problem restricted to colored
graphs with color multiplicities 2 and 3 is complete for
symmetric logarithmic space SL under many-one reductions. This
result improves the existing upper bounds for the problem.
We also show that the graph automorphism problem for
colored graphs with color classes of size 2
is equivalent to deciding whether an undirected graph has more than a single
connected component
and we prove that for color classes of size 3 the graph automorphism
problem is contained in SL.