I shall attempt to answer your last question.  

**Question:** Can we tell - and how - whether a given matrix with integer entries (and ∗ eventually) corresponds to a (generalized) regular coloring?

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] <cite authors="Telle, Jan Arne; Proskurowski, Andrzej">_Telle, Jan Arne; Proskurowski, Andrzej_, [**Algorithms for vertex partitioning problems on partial \(k\)-trees**](http://dx.doi.org/10.1137/S0895480194275825), SIAM J. Discrete Math. 10, No. 4, 529-550 (1997). [ZBL0885.68118](https://zbmath.org/?q=an:0885.68118).</cite>

[2] <cite authors="Belmonte, Rémy; Vatshelle, Martin">_Belmonte, Rémy; Vatshelle, Martin_, [**Graph classes with structured neighborhoods and algorithmic applications**](http://dx.doi.org/10.1016/j.tcs.2013.01.011), Theor. Comput. Sci. 511, 54-65 (2013). [ZBL1408.68109](https://zbmath.org/?q=an:1408.68109).</cite>

[3] <cite authors="Gerber, Michael U.; Kobler, Daniel">_Gerber, Michael U.; Kobler, Daniel_, [**Algorithms for vertex-partitioning problems on graphs with fixed clique-width.**](http://dx.doi.org/10.1016/S0304-3975(02)00725-9), Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). [ZBL1042.68092](https://zbmath.org/?q=an:1042.68092).</cite>

[4] <cite authors="Fiala, Jiří; Kratochvíl, Jan">_Fiala, Jiří; Kratochvíl, Jan_, [**Locally constrained graph homomorphisms – structure, complexity, and applications**](http://dx.doi.org/10.1016/j.cosrev.2008.06.001), Comput. Sci. Rev. 2, No. 2, 97-111 (2008). [ZBL1302.05122](https://zbmath.org/?q=an:1302.05122).</cite>