Regular graph colorings

Question

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

Answer 1

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.

Answer 2

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 [1] (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[2].

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 [4]). 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[3]

References

[1] 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.

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

[3] 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.

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