Group colorability of multigraphs (Q1759814): Difference between revisions

\textit{R. L. Brooks'} Theorem [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] states that for any connected undirected graph \(G\) with maximum degree \(\Delta\), the chromatic number of \(G\) is at most \(\Delta\) unless \(G\) is a clique or an odd cycle, in which case the chromatic number is \(\Delta+1\). The article under review studies group coloring as defined in the abstract. ``Let \(G\) be a multigraph with a fixed orientation \(D\) and let \(\Gamma\) be a group. Let \(F(G,\Gamma )\) denote the set of all functions \(f: E(G)\to \Gamma\). A multigraph \(G\) is \(\Gamma\)-colorable if and only if for every \(f\in F(G,\Gamma)\), there exists a \(\Gamma\)-coloring \(c:V(G)\to \Gamma\) such that for every \(e=uv\in E(G)\) (assumed to be directed from \(u\) to \(v\)), \(c(u)c(v)^{-1}\neq f(e)\). We define the group chromatic number \(\chi _g(G)\) to be the minimum integer \(m\) such that \(G\) is \(\Gamma\)-colorable for any group \(\Gamma\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigate the properties of \(\chi_g\) for multigraphs and prove an analogue to Brooks' Theorem.'' The main theorem in this article states: ``For any connected multigraph \(G\), \(\chi_g(G)\leq \Delta(G)+ 1\), where equality holds if and only if \(G\) is a cycle or a complete graph on \(n\) vertices in which each edge is replaced by \(k\) parallel edges, for some positive integers \(k\) and \(n\).'' Reviewer's remark: In quoting Brooks' theorem the authors omit the condition that the cycle be of odd length. This reviewer wonders whether this condition should also apply to the theorem of the article under review.