On closed modular colorings of regular graphs (Q2839638)

Let \(c : V(G) \rightarrow\mathbb Z_k\) be a (not necessarily proper) vertex coloring of a graph \(G\) using colors from the integers modulo \(k\). This induces a vertex coloring \(c' : V(G) \rightarrow {\mathbb Z}_k\) defined by \(c'(v) = \sum_{u \in N[v]} c(u)\), where \(N[v]\) is the closed neighborhood of \(v\). Two vertices \(u\), \(v\) are true twins if they have the same closed neighborhood and hence are adjacent and have \(c'(u) = c'(v)\). The coloring \(c\) is a closed modular \(k\)-coloring if \(c'(u) \neq c'(v)\) for every pair of adjacent vertices that are not true twins. The minimum \(k\) for which \(G\) has a closed modular \(k\)-coloring is called the closed modular chromatic number of \(G\), denoted \(\overline{mc}(G)\).NEWLINENEWLINEThe authors study the relation between \(\overline{mc}(G)\) and the chromatic number \(\chi(G)\). They show that for any \(b\) at least two and any \(a \leq b\), there is a connected graph \(G\) with true twins such that \(\overline{mc} (G) = a\) and \(\chi(G) = b\). In contrast, if \(G\) is connected and without true twins, then \(\overline{mc}(G) \geq \chi(G)\). They determine exact values of \(\overline{mc}(G)\) for several classes of graphs. For some regular complete multipartite graphs they give exact values of \(\overline{mc}(G)\) and offer bounds for other complete multipartite graphs.