The complexity of nonrepetitive edge coloring of graphs

2007/09/27 by Fedor Manin, Manin, Fedor
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.0709.4497

arxiv created 2007/12/06 · arxiv updated 2009/12/01

Abstract

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 Σ₂^p-complete. When we restrict to paths of lengths at most n, the problem becomes NP-complete for fixed n.

Related

• The nonrepetitive colorings of grids
• Nonrepetitive choice number of trees
• Nonrepetitive colorings of lexicographic product of graphs
• Complexity of Coloring Graphs without Paths and Cycles
• Classifying k-Edge Colouring for H-free Graphs