Notes on nonrepetitive graph colouring (Q1010826)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Notes on nonrepetitive graph colouring |
scientific article |
Statements
Notes on nonrepetitive graph colouring (English)
0 references
7 April 2009
0 references
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.
0 references