Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334294 | Theoretical Computer Science | 2005 | 13 Pages |
Abstract
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 Ï:E(G)âA, there exists a vertex-coloring c:V(G)âA with c(v)-c(u)â Ï(uv) for each oriented edge uv of G. We show that the decision problem whether a given graph has group chromatic number at most k is Î 2P-complete for each integer k⩾3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Král',