Nonrepetitive Graph Colouring

2020/09/04 by David R. Wood, David R Wood
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Graph #Graph theory #Limits and Structures in Graph Theory #Path (computing) #Scheduling and Timetabling Solutions #Sequence (biology) #Vertex (graph theory) #cs.DM #math.CO

paper · pdf · doi:10.37236/9777

published as Electronic J. Combinatorics DS24, 2021

arxiv created 2020/09/04 · openalex created_date 2020/09/11 · openalex publication_date 2021/09/10 · arxiv updated 2021/09/13 · openalex updated_date 2026/08/05

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.

Citations

• Lower bound of the hadwiger number of graphs by their average degree
• A partial k-arboretum of graphs with bounded treewidth
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colouring via entropy compression
• A note on the Thue chromatic number of lexicographic products of graphs
• Structure of Graphs with Locally Restricted Crossings
• Planar graphs have bounded queue-number