[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$.

**Examle**: $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?