Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ? In particular, it would be interesting to have conditions on this partial isomorphism that makes the problem polynomial.
This question arises from automata theory, where one approach to testing equivalence of two NFAs on alphabet $A$ is to compute their syntactic semigroups $M_1,M_2$ (of exponential size) together with functions $h_1:A\to M_1$, $h_2: A\to M_2$. Testing semigroup isomorphism is hard in the general case, but here we can do it polynomially, because $h_1,h_2$ already give us a partial isomorphism for a set of generators, which is enough.
For graphs, an obvious sufficent condition for such a partial isomorphism to make the problem polynomial would be "containing a covering set" (in the sense each edge contains a vertex in it) . Maybe there are more subtle conditions that would still work ?