Informace o publikaci

Group coloring and list group coloring are Pi(P)(2)-complete

Autoři

KRÁĽ Daniel NEJEDLY P

Rok publikování 2004
Druh Článek v odborném periodiku
Časopis / Zdroj MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS
Citace
Popis A graph G is A-l-choosable for an Abelian group A and an integer l < A if for each orientation of G, each edge-labeling phi : E(G) --> A and each list-assignment L : V(G) --> (A), there exists a vertex-coloring c : V(G) --> A with c(v) epsilon L(v) for each vertex v and with c(v) - c(u) not equal phi(uv) for each oriented edge uv of G. We prove a dichotomy result on the computational complexity of this problem. In particular, we show that the problem is Pi(2)(P)-complete if l greater than or equal to 3 for any group A and it is polynomial-time solvable if l = 1, 2. This also settles the complexity of group coloring for all Abelian groups.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info