The complexity of nonrepetitive coloring |
| |
| Authors: | Dániel Marx |
| |
| Institution: | a Department of Computer Science and Information Theory, Budapest University of Technology and Econonomics, Budapest H-1521, Hungary
b Department of Computer Science, DePaul University, Chicago, IL 60604, United States |
| |
| 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. |
| |
| Keywords: | Nonrepetitive coloring Thue chromatic number Polynomial hierarchy Complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
