Graph Isomorphism for Colored Graphs with Color Multiplicity Bounded by 3 Download as PDF


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.


dieter@cs.wisc.edu