Informace o publikaci
Group coloring and list group coloring are Pi(P)(2)-complete
| Autoři | |
|---|---|
| Rok publikování | 2004 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS |
| Citace | |
| Popis | 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. |