Title: |
The
Complexity of Nonrepetitive Coloring |

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] |