[Since I didn't get any feedback at MSE, I dare to post this question here, too.]
Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,n \rbrace$ of a graph $G$ regular when every vertex with color $c_i$ has the same number of neighbors with color $c_j$.
Call a coloring faithful when two vertices have the same color iff they are conjugate.
Observation: Every faithful coloring is regular (obviously) but not vice versa (maybe not so obvious).
The latter is (somehow) a generalization of the fact, that every vertex-transitive graph (with one conjugacy class only!) is regular, but not vice versa.
Consider the color adjacency matrix – or color matrix for short – with $c_{ij}$ being the number of neighbors of color $c_j$ of the vertices of color $c_i$.
Consider generalized color matrices with entries that don't have to be fixed integers but are allowed to be the Kleene star $*$ with $c_{ij} = *$ meaning that there may be arbitrarily many neighbors of color $c_j$ of the vertices of color $c_i$.
Generalized color matrices can be seen as a kind of graph grammar: they indicate – like a context-free grammar does – which and how many colors (or symbols) are allowed as neighbors of a given color (or symbol).
(Main differences: no distinguished start and terminal symbols, unordered neighbors.)
Like a context-free grammar defines a class of valid trees, a generalized color matrix defines a class of valid graphs, especially those which can be regularly colored in accordance with the color matrix.
Example: Color matrices $C$ with entries from $0, 1$ define the graphs which consist of $n$ copies of the graph with adjacency matrix $C$.
Example: $k\times k$ color matrices of the form $c_{ii} = 0, c_{ij} = *$ for $i\neq j$ define the usual $k$-colorable graphs.
Example: $1\times 1$ color matrices with $c_{00} = k$ define the usual $k$-regular graphs.
Question: Has this or a related kind of graph grammar been investigated before?
Question: Can we tell – and how – whether a given matrix with integer entries (and $*$ eventually) corresponds to a (generalized) regular coloring?
Best Answer
A matrix corresponds to a regular coloring if and only if it is a symmetric matrix times a diagonal matrix.
Only if: Take a matrix $A$ such that $a_{ii}$ is the number of vertices with the $i$th color and $a_{ij}=0$ for $i\neq j$. Then $CA$ is symmetric, because $c_{ij}a_{jj}$ is the number of edges between vertices with the $i$th color and vertices with the $j$th color.
If: Choose a diagonal $A$ such that $CA$ is symmetric. Since $c_{ij}a_{jj}=c_{ji}a_{ii}$, $a_{ii}/a_{jj}=c_{ij}/c_{ji}$, so the ratio between elements of the diagonal is rational, so we can take them all to be integers by multiplying by a constant. Form a graph whose number of vertices of color $i$ is $a_{ii}$. For each pair of colors, the adjacency matrix mandates a certain number of edges from each color going to the other color. Because $CA$ is symmetric, these are the same number of edges, and so we can connect the edges coming from vertices of color $i$ to the edges coming from vertices of color $j$ arbitrarily.