Complexity of pattern coloring of cycle systems
|Článek v odborném periodiku
|Časopis / Zdroj
|GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
|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.