## DIMACS TR: 2002-06

## On Pattern Coloring of Cycle Systems

### Authors: Zdenek Dvorak, Jan Kara, Daniel Kral, Ondrej Pangrac

**
ABSTRACT
**

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