I shall attempt to answer whether (generalized) regular colouring or a related kind of graph grammar been investigated before, mostly from a complexity theoretic perspective (rather than studying matrices that are 'realizable' by a regular colouring).

A notion stronger than generalized regular colouring is there in the literature. Given a $q\times q$ matrix $D_q$ whose entries are subsets of $\{0,1,2,\dots\}$ and a graph $G$, a *$D_q$-partition* of $G$ is a partition of the vertex set of $G$ into sets $V_{i}$ ($1\leq i\leq q$) such that for all $i$ and $j$ every vertex in $V_{i}$ has exactly $D_q(i,j)$ neighbours in $V_j$.

Note: Here $D_q(i,j)$ denotes the $(i,j)$th entry of $D_q$.

The $D_q$-partition problem belongs to the Locally Checkable Vertex Subset and Partitioning problems (LC-VSP) framework of Telle and Proskurowski [1] (also see Telle's thesis *Vertex Partitioning Problems: Characterization, Complexity and Algorithms on Partial k-Trees*).

**Assume that each entry of $D_q$ is either finite or cofinite**. Then, **there is an FPT algorithm** with parameter treewidth (or cliquewidth) to test whether a graph admit a $D_q$-partition. In particular, if the graph has bounded treewdith (or cliquewidth), then we can test in polynomial time. Moreover, the problem also admits a polynomial time algorithm in a number of graph classes including interval graphs, permutaiton graphs, trapezoid graphs, convex graphs and Dilworth-k graphs[2].

It is known that testing for a $D_q$ partition is NP-ocmplete even when the entries are $\{0\}$ or $\{1\}$ (basically adjacency matrix of some graph $H$). In this case a graph $G$ is said to have a $D_q$ partition iff $G$ has a *locally bijective homormorphism* to $H$ (see [4]). When $H$ is a regular graph, in almost all cases, the problem is NP-complete. **Therefore, regular coloring problem is NP-complete**.

PS: If every entry in $D_q$ is a set of consecutive integers (true for (generalized) regular colouring), then the problem also fits in the framework of Gerber and Kobler[3]

## References

[1] *Telle, Jan Arne; Proskurowski, Andrzej*, **Algorithms for vertex partitioning problems on partial (k)-trees**, SIAM J. Discrete Math. 10, No. 4, 529-550 (1997). ZBL0885.68118.

[2] *Belmonte, Rémy; Vatshelle, Martin*, **Graph classes with structured neighborhoods and algorithmic applications**, Theor. Comput. Sci. 511, 54-65 (2013). ZBL1408.68109.

[3] *Gerber, Michael U.; Kobler, Daniel*, **Algorithms for vertex-partitioning problems on graphs with fixed clique-width.**, Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). ZBL1042.68092.

[4] *Fiala, Jiří; Kratochvíl, Jan*, **Locally constrained graph homomorphisms – structure, complexity, and applications**, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). ZBL1302.05122.

1more comment