Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Humboldt-Universität zu Berlin | Mathematisch-Naturwissenschaftliche Fakultät | Institut für Informatik | Komplexität und Kryptografie | Publikationen | Abstracts | The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3

The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3

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.

Ps-File: The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3