Publication details
Complexity of pattern coloring of cycle systems
| Authors | |
|---|---|
| Year of publication | 2002 |
| Type | Article in Periodical |
| Magazine / Source | GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE |
| Citation | |
| Description | 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. |