As an answer from @thorumur's comment:
You might find Szabolcs' wonderful IGraph package useful, possibly the function IGGetSubisomorphism in particular, which (from the documentation) seems to find a mapping that realizes its first argument as a subgraph of its second argument if such a mapping exists.
g = PetersenGraph;
(* get the 3d coordinates of the graph vertices *)
coords = Append[#, 0] & /@ GraphEmbedding[g];
points = Point[coords];
(* create lines between the edges *)
connections = EdgeList[g];
lines = Line[coords[[#]]] & /@ (connections /. UndirectedEdge -> List);
(* generate some signals on each vertex as lines pointing upwards *)
Graph objects render as a visual representation by default. This is merely for convenience, not a way to visualize the graph. If you want to explicitly visualize it, use GraphPlot.
Once the graph gets large, visualization becomes expensive. I wouldn't want my work to be slowed down (or at worst: the notebook interface hang) when working with large graphs ...
We can use AdjacencyList[g,v] to find the neighbors of a vertex v in graph g.
Construct a subgraph of g formed by neighbors of the focal node.
Then we can use FindHamiltonianPath on the subgraph starting with the east neighbor and ending with the south-east neighbor of the focal node to get the neighbors in desired order.
Use the desired list of colors and ...
Here's what I came up with. It's messy, but it seems to work. I'm sure someone would be able to do a better implementation. I don't even know how to store a result so I don't have to type out cpF[cpF[VertexList[g1], VertexList[g2]],cpF[VertexList[g1], VertexList[g2]]], nor can I figure out why Cartesian Product of a list isn't working normally, thus why I ...