The complexity of nonrepetitive edge coloring of graphs

Fedor Manin

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 t…