Publication details
Group coloring and list group coloring are Pi(P)(2)-complete
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Periodical |
| Magazine / Source | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS |
| Citation | |
| Description | A graph G is A-l-choosable for an Abelian group A and an integer l < A if for each orientation of G, each edge-labeling phi : E(G) --> A and each list-assignment L : V(G) --> (A), there exists a vertex-coloring c : V(G) --> A with c(v) epsilon L(v) for each vertex v and with c(v) - c(u) not equal phi(uv) for each oriented edge uv of G. We prove a dichotomy result on the computational complexity of this problem. In particular, we show that the problem is Pi(2)(P)-complete if l greater than or equal to 3 for any group A and it is polynomial-time solvable if l = 1, 2. This also settles the complexity of group coloring for all Abelian groups. |