Dániel Marx, Marcus Schaefer: The complexity of nonrepetitive coloring. Discret. Appl. Math. 157(1): 13-18 (2009)