Suppose you are given two graphs with $v$ vertices and wish to check whether they are isomorphic are not. One possible way to do this is to enumerate all possible permutations of the $v$ vertices and see if any of these permutations create a bijection between the edges and vertices of the graphs. However, this type of algorithm takes a global view of the problem, I was wondering if there was an algorithm that took a more local view. That is, if you input a graph into this algorithm it will output a specific vertex (up to automorphism of course) regardless of how the vertices are labeled.
If we called the local view algorithm $P(G)$, then the full algorithm to check isomorphism between graphs $G$ and $H$ would work as follows:
$1)$ Run $P(G)$ and $P(H)$
$2)$ Store the vertices outputted as equivalent vertices
$3)$ Remove these vertices from $G$ and $H$. Return to step $1)$
After $v$ steps, you will have a list of $v$ pairs of equivalent vertices. You then check whether this list actually describes an isomorphism between the graphs. If it does, the graphs are isomorphic, if not then they are not.
Such an algorithm $P(G)$ is not computable in polynomial time as the other steps in the algorithm above can be computed in polynomial time. If this were not the case, then graph isomorphism would be computable in polynomial time (this is not currently known). Here is an example for a specific type of graph: Suppose $G$ and $H$ are graphs such that every vertex has a unique degree and every vertex is only connected to itself. Then $P(G)$ simply outputs the vertex with the largest degree.
Reiterating the question: Does such a local algorithm exist for all graphs?