Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419785 | Discrete Applied Mathematics | 2009 | 6 Pages |
Abstract
A coloring of a graph is nonrepetitive if the graph contains no path that has a color pattern of the form xxxx (where xx 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 xxxx up to a fixed length kk of xx.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dániel Marx, Marcus Schaefer,