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

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?

• 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

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.

I shall attempt to answer whether (generalized) regular colouring or a related kind of graph grammar been investigated before, mostly from a complexity theoretic perspective (rather than studying matrices that are 'realizable' by a regular colouring).

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  (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.

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 ). 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

## References

 Telle, Jan Arne; Proskurowski, Andrzej, Algorithms for vertex partitioning problems on partial (k)-trees, SIAM J. Discrete Math. 10, No. 4, 529-550 (1997). ZBL0885.68118.

 Belmonte, Rémy; Vatshelle, Martin, Graph classes with structured neighborhoods and algorithmic applications, Theor. Comput. Sci. 511, 54-65 (2013). ZBL1408.68109.

 Gerber, Michael U.; Kobler, Daniel, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). ZBL1042.68092.

 Fiala, Jiří; Kratochvíl, Jan, Locally constrained graph homomorphisms – structure, complexity, and applications, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). ZBL1302.05122.

• What OP called as regular coloring is called a regular partition in Kratochvil, Regular codes in regular graphs are difficult (1994) – Cyriac Antony Mar 25 at 11:39