DIMACS TR: 2002-06

On Pattern Coloring of Cycle Systems

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


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