A canonical labeling, also called a canonical form, of a graph is a graph which is isomorphic to and which represents the whole isomorphism class of (Piperno 2011). The complexity class of canonical labeling
is not known.
Efficient labeling methods yield an efficient tests for isomorphic
graphs, as provided for example by nauty, Traces, bliss, and other software implementations.
Junttila, T. and Kaski, P. "Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs." In Proceedings of the
Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on
Analytic Algorithms and Combinatorics (Ed. D. Applegate, G. S. Brodal,
D. Panario, and R. Sedgewick.) SIAM: pp. 135-149, 2007.McKay,
B. "Practical Graph Isomorphism." Congr. Numer.30, 45-87,
1981. http://cs.anu.edu.au/~bdm/nauty/pgi.pdf.McKay,
B. and Piperno, A. "Practical Graph Isomorphism, II." 8 Jan 2013. http://arxiv.org/abs/1301.1493.Piperno,
A. "Search Space Contraction in Canonical Labeling of Graphs." 26 Jan 2011.
http://arxiv.org/abs/0804.4881.
is a graph 
which is isomorphic to 
and which represents the whole isomorphism class of 
(Piperno 2011). The complexity class of canonical labeling
is not known.
