This is a twist on standard subgraph isomorphism. Say I have two graphs $G(V,E)$ and $H(V',E')$ and the vertices in each graph are colored with one of $t$ colors. The subgraph isomorphism exists if there exists a mapping from $f:V\rightarrow V_0\subset V'$ s.t. $\forall {v_1,v_2}\in E \iff {f(v_1),f(v_2)}\in E'$ and $Color(v)=Color(f(v)) \forall v \in V$ (i.e. the colors must match under the mapping). I can solve this problem with ILP (integer linear program) fairly easily.
Rather, my question is can we find a new coloring (or permutation of the existing colors) of G (with $t$ color choices for each vertex) such that no subgraph isomorphism (with coloring preserved) exists between G and H.
My naive approach searches for the solution by using the subgraph isomorphism ILP as a subroutine. My question is whether an ILP could be constructed to directly solve this. Any thoughts would be much appreciated.