The complexity of nonrepetitive edge coloring of graphs
| dc.creator | Manin, Fedor | |
| dc.date | 2007-09-27 | |
| dc.date | 2007-12-06 | |
| dc.date.accessioned | 2026-07-07T08:47:21Z | |
| dc.date.available | 2026-07-07T08:47:21Z | |
| dc.description | 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 $Σ_2^p$-complete. When we restrict to paths of lengths at most $n$, the problem becomes NP-complete for fixed $n$. | |
| dc.identifier | https://arxiv.org/abs/0709.4497 | |
| dc.identifier | http://arxiv.org/abs/0709.4497 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/143569 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2 | |
| dc.title | The complexity of nonrepetitive edge coloring of graphs | |
| dc.type | text |