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)\ne 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 $\ge 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.