  A squarefree word is a sequence $w$ of symbols such that there are no strings
$x, y$, and $z$ for which $w=xyyz$. A nonrepetitive coloring of a graph is an
edge coloring in which the sequence of colors along any open path is
squarefree. We show that determining whether a graph $G$ has a nonrepetitive
$k$-coloring is $\Sigma_2^p$-complete. When we restrict to paths of lengths at
most $n$, the problem becomes NP-complete for fixed $n$.
