# Regular graph colorings

[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?

• Your first example is not quite right, I think. Consider the color matrix which is the adjacency matrix of the $3$-cycle. Any disjoint union of $3n$-cycles is a valid graph for this color matrix. In general, you're looking at unions of covering spaces of the graph with that adjacency matrix. – Will Sawin Aug 3 '12 at 11:42
• If the color matrix has no $*$s, every eigenvalue of the color matrix must be an eigenvalue of the graph's adjacency matrix, and the largest eigenvalue of the color matrix must be the largest eigenvalue of the color matrix. You could consider expander graph - like notions with a spectral gap around one or all of these eigenvalues. – Will Sawin Aug 3 '12 at 11:47
• Also posted, without indication here nor there, to math.stackexchange.com/questions/178053/regular-graph-colorings. How rude. – Gerry Myerson Aug 3 '12 at 12:17
• Sorry for that. – Hans-Peter Stricker Aug 3 '12 at 12:25
• Isn't a "regular coloring" just the same as equitable partition? – Felix Goldberg Sep 6 '12 at 22:12

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.