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). The feasible set of a cycle system is the set of all l's such that there exists a proper coloring of it using exactly l colors.
For all combinations of a pattern set P and a number l, we either find
a polynomial algorithm or prove NP--completeness of the problem whether
a given cycle system with a set of patterns P can be colored by at most l
colors. We further construct a cycle system with a prescribed feasible set
for almost every set of patterns containing only two different letters.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-06.ps.gz
DIMACS Home Page