Consider the following setting.
- We are given a simple undirected graph $G$ and a coloring $c:V(G) \mapsto \{0,1\}.$
- We can compute the canonical labelling and $\rm{Aut}(G)$ efficiently.
What I would like to compute is the canonical labelling/orbits of the automorphism group of $G$ that respects the coloring $c.$ That is a permutation $f:V(G) \mapsto V(G)$ is an automorphism if $$v \sim u \iff f(v) \sim f(u) \quad \mbox{and} \quad c(u) = c(v).$$
I think that one way to do so is to let $k = \Delta(G)+1$ and join to each vertex $v \in V(G)$ to the central vertex of a star of order $k+c(v).$
What I am wondering is
Is there a more efficient way to obtain the orbits/canonical labeling for this problem?