While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.
But what happens if we assume that both $G_1$ and $G_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)?
Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G_1 \cup G_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. 401-411).