(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.)

Some basic definitions for completeness:

Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph isomorphism problem (GI) asks whether there exists a one-to-one mapping $\sigma: V_1 \rightarrow V_2$ such that $(a, b) \in E_1 \Rightarrow (\sigma(a), \sigma(b)) \in E_2$ for $a,b \in V_1$.

This can equivalently be stated using linear algebra as follows: Given two graphs $G_1$ with adjacency matrix $A$ and $G_2$ with adjacency matrix $B$, is there a permutation matrix $P$ that satisfies the following: $$ P A P^T = B $$

Now consider a generalized version of GI where each node can have a color (given by $color(a))$ and multiple nodes can share the same color i.e. number of colors $k$ can be less than the total number of vertices $n$. We can think of $color$ as a mapping $V \rightarrow \{1,...,k\}$ where $k \leq n$. Each graph can have its own color mapping so lets denote the colors for $G_i$ by $color_i$. In this setting, besides the required edge mapping by GI (as specified in the first paragraph above), we have the following additional restriction on $\sigma$:

$$ color_1(a) = color_1(b) \Rightarrow color_2(\sigma(a)) = color_2(\sigma(b)) $$

Notice that nodes can be mapped to a color different than their original one, but the restriction is that same color nodes should always be mapped to the same target color.

Clearly this problem is at least as hard as GI, because GI is the special case where each node has its own unique color in both graphs.

My question is, can this problem also be formulated using permutation matrices (and/or some other linear algebra tools) similar to GI above?

I’m probably missing some very simple formulation right now.

Thanks in advance!