Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices.
Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$.
The edge set between $G_1$ and $G_k$ is denoted by $R_{1,k}$. We color/label all vertices of $G_1$ and $G_k$ as $r_{1,k}$.
Similarly, we find all possible permutation of $G_i, G_j$ and if they have edge set exactly like $R_{1,k}$ we color/label all vertices of $G_i$ and $G_j$ as $r_{1,k}$.
This is not "traditional" and "usual" coloring where two adjacent vertices have different color.
Question: What kind of vertex coloring is this? Does it exist in any graph theory literature?
Note:
- $R_{i,k}$ is a set of edges. If we look at the adjcency matrix, $R_{i,k}$ is a non symmetric matrices of $k \times k$ dimension.
Let, $k=3$ and $n=9$, then $x=3$, the adjacency matrix of graph $H$ would look like- $$G = \begin{bmatrix} G_{(3)} & R_{(3, 2)} & R_{(3,1)} \\ R_{(3,2)}^{T} & G_{(2)} & R_{(2,1)} \\ R_{(3,1)}^{T} & R_{(2,1)}^{T} &G_{1} \end{bmatrix}$$
Now, $R_{2,1}$ is a a non symmetric matrices of $3 \times 3$ dimension.
Let, $R_{1,2} = \begin{bmatrix} 0 & 1 &0 \\ 0 & 0 &0 \\ 0 & 0 &0\\ \end{bmatrix}$. So, $R_{2,1}$ is set of edges that tells you $G_1$ is connected with $G_2$ with only one edge. For this we color all vertices of $G_1,G_2 $ as $r_{1,2}$ (considering it a s label / color). Again we see that $R_{1,3} = \begin{bmatrix} 0 & 0 &0 \\ 0 & 1 &0 \\ 0 & 0 &0\\ \end{bmatrix}$. We will color all vertices of $G_3 $ as $r_{1,2}$ if $G_3$ is isomorphic $G_2 $ after swapping vertices of $G_3$. It would make-
$$R_{1,3} = \begin{bmatrix} 0 & 1 &0 \\ 0 & 0 &0 \\ 0 & 0 &0\\ \end{bmatrix} =R_{1,2}$$.
So, then we would color all vertices of $G_3$ as $r_{1,2}$, otherwise it would be another color $r_{1,3}$.
- "Probably" I am reinventing old things. It could be Weisfeiler-Lehman Method method where $k$ vertices get "individualized".
Also, in the paper, "Isomorphism of graphs of bounded valence can be tested in polynomial time" by Eugene M. Luks (Journal of Computer and System Sciences, Volume 25, Issue 1, (1982), Pages 42-65) mifht have the same coloring process, but I am not sure, thus looking for expert-help.
3."Does "exactly like" mean isomorphic as graphs?"
-Yes
4."Or isomorphic as graphs with the additional structure indicating which vertices are in which of the subgraphs?" -- All sub graphs with vertices (colored with $r_{a,b}$), are isomorphic with the additional structure $R_{i,k}$ ( all subgraph has exactly same $R_{i,k} =R_{a,b}$ )
