Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours

Abstract

A vertex colouring of a graph is \emph{nonrepetitive} if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The \emph{nonrepetitive chromatic number} of a graph $G$ is the minimum integer $k$ such that $G$ has a nonrepetitive $k$-colouring. Whether planar graphs have bounded nonrepetitive chromatic number is one of the most important open problems in the field. Despite this, the best known upper bound is $O(\sqrt{n})$ for $n$-vertex planar graphs. We prove a $O(\log n)$ upper bound.

References in corpus (3)

• Nonrepetitive Colouring via Entropy Compression
• The complexity of nonrepetitive edge coloring of graphs
• A note on non-repetitive colourings of planar graphs

Cited by in corpus (10)

• Layered Separators in Minor-Closed Graph Classes with Applications
• Planar graphs have bounded nonrepetitive chromatic number
• Nonrepetitive edge-colorings of trees
• The Thue choice number versus the Thue chromatic number of graphs
• Nonrepetitive graph colouring
• Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
• Plane Graphs are Facially-non-repetitively $10^{4\cdot 10^7}$-Choosable
• Nonrepetitive choice number of trees
• Avoiding large squares in trees and planar graphs
• Online version of the theorem of Thue