Informace o publikaci
Group coloring is Pi(P)(2)-complete
| Autoři | |
|---|---|
| Rok publikování | 2005 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.tcs.2005.09.033 |
| Klíčová slova | group coloring; group connectivity; nowhere-zero flows; Pi(P)(2)-completeness |
| Popis | 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. |