Group coloring is Î 2P-complete

The group chromatic number of a graph G is the smallest integer k such that for every Abelian group A of order at least k, every orientation of G and every edge-labeling ϕ:E(G)→A, there exists a vertex-coloring c:V(G)→A with c(v)-c(u)≠ϕ(uv) for each oriented edge uv of G. We show that the decision problem whether a given graph has group chromatic number at most k is Π2P-complete for each integer k⩾3.