Report Number: CS-TR-79-706
Institution: Stanford University, Department of Computer Science
Title: Graph 2-isomorphism is NP-complete
Author: Yao, F. Francis
Date: January 1979
Abstract: Two graphs G and G' are said to be k-isomorphic if their edge sets can be partitioned into E(G) = $E_1 \cup E_2 \cup ... \cup E_k$ and E(G') = ${E'}_1 \cup {E'}_2 \cup ... \cup {E'}_k$ such that as graphs, $E_i$ amd ${E'}_i$ are isomorphic for $1 \leq i \leq k$. In this note we show that it is NP-complete to decide whether two graphs are 2-isomorphic.
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/706/CS-TR-79-706.pdf