Group Coloring and List Group Coloring Are
Daniel Král͏̌, Pavel Nejedlý · 2004
A graph G is A-� -choosable for an Abelian group A and an integer � ≤| A| if for each orientation of G, each edge-labeling ϕ : E(G) → A and each list-assignment L : V (G) → A � , there exists a vertex-coloring c : V (G) → A with c(v) ∈ L(v) for each vertex v and with c(v) − c(u) � ϕ(uv) for each oriented edge uv of G.W e prove a dichotomy result on the computational complexity of this problem. In particular, we show that the problem is Π P -complete if � ≥ 3 for any group A and it is polynomial-time solvable if � =1 , 2. This also settles the complexity of group coloring for all Abelian groups.