Nonrepetitive Graph Colouring

Research output: Contribution to journalArticleResearchpeer-review


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.
Original languageEnglish
Article numberDS24
Number of pages78
JournalThe Electronic Journal of Combinatorics
VolumeDynamic Surveys
Publication statusPublished - 10 Sept 2021

Cite this