Publication details

Group coloring is Pi(P)(2)-complete


KRÁĽ Daniel

Year of publication 2005
Type Article in Periodical
Magazine / Source Theoretical Computer Science
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.

You are running an old browser version. We recommend updating your browser to its latest version.

More info