Nonrepetitive graph colouring

Abstract

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.

References in corpus (14)

• Acyclic edge-coloring using entropy compression
• Characterisations and Examples of Graph Classes with Bounded Expansion
• Planar graphs have bounded queue-number
• Nonrepetitive Colouring via Entropy Compression
• A new approach to nonrepetitive sequences
• A Unified Approach to Distance-Two Colouring of Graphs on Surfaces
• Planar graphs have bounded nonrepetitive chromatic number
• Vertex coloring of plane graphs with nonrepetitive boundary paths
• Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
• Notes on Graph Product Structure Theory
• Pathwidth and nonrepetitive list coloring
• Nonrepetitive edge-colorings of trees
• Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
• A note on the Thue chromatic number of lexicographic products of graphs