Publication details
Group coloring is Pi(P)(2)-complete
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | Theoretical Computer Science |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.tcs.2005.09.033 |
| Keywords | group coloring; group connectivity; nowhere-zero flows; Pi(P)(2)-completeness |
| Description | 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 (p : E(G) -> A, there exists a vertex-coloring c : V(G) -> A with c(v) - c(u) not equal rho(uv) for each oriented edge u v of G. We show that the decision problem whether a given graph has group chromatic number at most k is II2P-complete for each integer k >= 3. (c) 2005 Elsevier B.V. All rights reserved. |