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

KRÁĽ, Daniel. Group coloring is Pi(P)(2)-complete. Theoretical Computer Science. AMSTERDAM: North Holland, 2005, roč. 349, č. 1, s. 99-111. ISSN 0304-3975. Dostupné z: https://dx.doi.org/10.1016/j.tcs.2005.09.033.

Základní údaje

Originální název

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

Autoři

KRÁĽ, Daniel

Vydání

Theoretical Computer Science, AMSTERDAM, North Holland, 2005, 0304-3975

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.743

DOI

http://dx.doi.org/10.1016/j.tcs.2005.09.033

UT WoS

000233783000010

Klíčová slova anglicky

group coloring; group connectivity; nowhere-zero flows; Pi(P)(2)-completeness

---

Anotace

V originále

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.