Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge (Q2665958)

Summary: 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^\prime(G))\) subdivisions per edge are enough, where \(\pi^\prime(G)\) is the nonrepetitive chromatic index of \(G\). This answers a question of \textit{D. R. Wood} [``Nonrepetitive graph colouring'', Electron. J. Comb., Dynamic Surveys, Article ID \#DS24, 78 p. (2021; \url{doi:10.37236/9777})] and improves a similar result of \textit{A. Pezarski} and \textit{M. Zmarz} [ibid. 16, No. 1, Research Paper N15, 7 p. (2009; Zbl 1165.05325)] that stated the existence of at least one 3-colorable subdivision with a linear number of subdivision vertices per edge.