J 2002

Complexity of pattern coloring of cycle systems

DVORAK, Z; J KARA; Daniel KRÁĽ a O PANGRAC

Základní údaje

Originální název

Complexity of pattern coloring of cycle systems

Autoři

DVORAK, Z; J KARA; Daniel KRÁĽ a O PANGRAC

Vydání

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, BERLIN, SPRINGER-VERLAG BERLIN, 2002, 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:41, Mgr. Darina Boukalová

Anotace

V originále

A k-cycle system is a system of cyclically ordered k-tuples of A finite set. A pattern is a sequence of letters. A coloring of a k-cycle system with respect to a set of patterns of length k is-proper iff each cycle is colored consistently with. one of the patterns, i.e. the same/distinct letters correspond to the same/distinct color(s). We prove a:dichotomy result on the complexity of coloring a given cycle system with a fixed set of patterns P by at most l colors and discuss possible generalizations.