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 $O(\log |V(G)|)$, $H$ is nonrepetitively 3-colorable. In fact, we show that $O(\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 Wood and improves a similar result of Pezarski and Zmarz that stated the existence of at least one 3-colorable division with a linear number of subdivision vertices per edge.

References in corpus (1)

• Entropy compression method applied to graph colorings