- Authors: A. Lal and D. van Melkebeek.
- Reference: Technical Report # 1523, Department of Computer Sciences,
University of Wisconsin-Madison, 2005.
Abstract
The colored graph isomorphism problem is a restricted version of the general
graph isomorphism problem that involves deciding the existence of a
color preserving isomorphism between a pair of colored graphs.
We study this problem for graphs whose color multiplicity is bounded by three
(3-GI).
We show how to solve 3-GI in logarithmic space, as well as the
problem of deciding the existence of a non-trivial color preserving
automorphism on a graph with color multiplicity bounded by three.
In previous work by other authors, a proof of 3-GI in symmetric logspace
(which we now know to be the same as L) has been given but the proof is
incorrect. We present a counter example.
