Informace o publikaci
Complexity of pattern coloring of cycle systems
| Autoři | |
|---|---|
| Rok publikování | 2002 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE |
| Citace | |
| Popis | 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. |