The complexity of nonrepetitive edge coloring of graphs
Manin, Fedor
Original · EN
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 Σ₂ᵖ-complete. When we restrict to paths of lengths at most n, the problem becomes NP-complete for fixed n.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.