Title: The Complexity of Nonrepetitive Coloring
Published: July 2007
Authors: Daniel Marx, Marcus Schaefer
Abstract: A coloring of a graph is nonrepetitive if the graph contains no path that has a color pattern of the form xx (where x is a sequence of colors). We show that determining whether a particular coloring of a graph is nonrepetitive is coNP-hard, even if the number of colors is limited to four. The problem becomes fixed-parameter tractable, if we only exclude colorings xx up to a fixed length k of x.
Full Paper: [postscript, pdf]