# Regular graph colorings

[I worked this question over and posted it to MO, too.]

Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,|V(G)| \rbrace$ of the vertices of a graph $G$ regular when every vertex of color $c_i$ has the same number of neighbors of color $c_j$.

Observation: A graph is regularly 1-colorable iff it is regular.

Call a coloring consistent when conjugate vertices have the same color.

Call a coloring strongly consistent when it reflects conjugacy of vertices, i.e. two vertices have the same color iff they are conjugate.

Observation: Every strongly consistent coloring is regular.

Consider the color adjacency matrix - or color matrix for short - $C$ with $c_{ij}$ being the number of neighbors of color $c_j$ of the vertices of color $c_i$.

Observation: For an asymmetric graph $G$ with $|Aut(G)| = 1$ a strongly consistent color matrix is equal up to permutations to its adjacency matrix.

Consider generalized color matrices with entries that are not fixed integer values but are allowed to be the Kleene star with $c_{ij} = *$ meaning that there may be arbitrary many neighbors of color $c_j$ of the vertices of color $c_i$.

Observation: Color matrices of the form $c_{ii} = 0, c_{ij} = *$ for $i\neq j$ correspond to the usual proper graph colorings.

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 color matrix defines a class of valid 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 regular coloring, ie. has a model?

Question: Can we tell - and how - whether a given color matrix corresponds to a strongly consistent coloring?

-
Also posted, without notice at either site, to mathoverflow.net/questions/103857/regular-graph-colorings. –  Gerry Myerson Aug 3 '12 at 12:18
Sorry for that. –  Hans Stricker Aug 3 '12 at 12:25