Paper Info
Title
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
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.
Year
DOI
Venue
2002
10.1007/3-540-45841-7_9
STACS
Keywords
Field
DocType
single connected component,color classes,existing upper bound,symmetric logarithmic space sl,color multiplicity,undirected graph,many-one reduction,graph isomorphism problem,graph isomorphism,color class,colored graphs,graph automorphism problem,upper bound
Graph automorphism,Discrete mathematics,Block graph,Combinatorics,Vertex-transitive graph,Line graph,Edge-transitive graph,Graph isomorphism,Graph homomorphism,Symmetric graph,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-43283-3
2
0.40
References 
Authors
13
2
Name
Order
Citations
PageRank
Johannes Köbler158046.51
Jacobo Torán256449.26