Group Colorability of Graphs

Abstract

Let \(G = (V, E)\) be a graph and \(A\) a non-trivial Abelian group, and let \(\mathcal{F}(G, A)\) denote the set of all functions \(f: E(G) \to A\). Denote by \(D\) an orientation of \(E(G)\). Then \(G\) is \(A\)-colorable if and only if for every \(f \in \mathcal{F}(G, A)\) there exists an \(A\)-coloring \(c: V(G) \to A\) such that for every \(e = (x,y) \in E(G)\) (assumed to be directed from \(x\) to \(y\)), \(c(x) – c(y) \neq f(e)\). If \(G\) is a graph, we define its group chromatic number \(\chi_1(G)\) to be the minimum number \(m\) for which \(G\) is \(A\)-colorable for any Abelian group \(A\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigated the properties of the group chromatic number, proved the Brooks Type theorem for \(\chi_1(G)\), and characterized all bipartite graphs with group chromatic number at most \(3\), among other things.