J 2004

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

KRÁĽ, Daniel a P NEJEDLY

Základní údaje

Originální název

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

Autoři

KRÁĽ, Daniel a P NEJEDLY

Vydání

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS, BERLIN, SPRINGER-VERLAG BERLIN, 2004, 0302-9743

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í

Označené pro přenos do RIV

Ne

UT WoS

Změněno: 6. 11. 2020 12:36, Mgr. Darina Boukalová

Anotace

V originále

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.