BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-706
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Graph 2-isomorphism is NP-complete
        TYPE:: Technical Report
      AUTHOR:: Yao, F. Francis
        DATE:: January 1979
       PAGES:: 13
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-706