
arXiv: 2009.02001
A vertex colouring of a graph $G$ is nonrepetitive if $G$ contains no path for which the first half of the path is assigned the same sequence of colours as the second half. Thue's famous theorem says that every path is nonrepetitively 3-colourable. This paper surveys results about nonrepetitive colourings of graphs. The goal is to give a unified and comprehensive presentation of the major results and proof methods, as well as to highlight numerous open problems.
walk-nonrepetitive colourings, FOS: Computer and information sciences, Coloring of graphs and hypergraphs, Discrete Mathematics (cs.DM), FOS: Mathematics, bounded degree graphs, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
walk-nonrepetitive colourings, FOS: Computer and information sciences, Coloring of graphs and hypergraphs, Discrete Mathematics (cs.DM), FOS: Mathematics, bounded degree graphs, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
