Group colorability of multigraphs
\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.
- Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions
- Graph polynomials and group coloring of graphs
- An inequality for the group chromatic number of a graph
- On group chromatic number of graphs
- A coloring property for countable groups
- A dual version of the brooks group coloring theorem
- Group chromatic number of Halin graphs
- A note on group colorings and group structure
- scientific article; zbMATH DE number 2188403 (Why is no real title available?)
- Polynomials counting group colorings in graphs
- Group coloring is \(\Pi_2^{\text{P}}\)-complete
This page was built for publication: Group colorability of multigraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759814)
