Nonrepetitively 3-Colorable Subdivisions of Graphs with a Logarithmic Number of Subdivisions per edge

Abstract

We show that for every graph $G$ and every graph $H$ obtained by subdividing each edge of $G$ at least $\Omega(\log |V(G)|)$ times, $H$ is nonrepetitively 3-colorable. In fact, we show that  $\Omega(\log \pi'(G))$ subdivisions per edge are enough, where $\pi'(G)$ is the nonrepetitive chromatic index of $G$. This answers a question of Wood and improves a similar result of  Pezarski and Zmarz that stated the existence of at least one 3-colorable subdivision with a linear number of subdivision vertices per edge.