Notes on nonrepetitive graph colouring (Q1010826)

Summary: A vertex colouring of a graph is nonrepetitive on paths if there is no path \(v_1,v_2,\dots,v_{2t}\) such that \(v_i\) and \(v_{t+i}\) receive the same colour for all \(i=1,2,\dots,t\). We determine the maximum density of a graph that admits a \(k\)-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree \(\Delta\) has a \(f(\Delta)\)-colouring that is nonrepetitive on walks. We prove that every graph with treewidth \(k\) and maximum degree \(\Delta\) has a \(O(k\Delta)\)-colouring that is nonrepetitive on paths, and a \(O(k\Delta^3)\)-colouring that is nonrepetitive on walks.