I have consulted the literature concerning graph isomorphism algorithms, and all papers I could find involve finding a canonical representation of a graph. So to decide whether two graphs are isomorphic, you just check if they have the same canonical representation (i.e. the same equivalence class).
There is, also, an other way to proceed: try to build explicitly the isomorphism between the two graphs, and answer Yes or No depending on the success of the task. One can think, for instance, to a constructive algorithm that incrementally build a bijection, using backtracking.
I was not able to find any literature related to the second topic. I understand that canonical representation is a better idea in general, but I am quite surprised that nobody ever tried to tackle the constructive approach. Maybe it is too naive ? My question is: do you know any literature on that topic, that I could have missed ?