Planar graphs have bounded nonrepetitive chromatic number

The following seemingly simple question with surprisingly many connections to various problems in computer science and mathematics can be traced back to the beginning of the 20th century to the work of Axel Thue: How many colours are needed to colour the positive integers so that no two consecutive segments of the same length have the same colour pattern? Clearly, at least three colours are needed.

Suprisingly, three colours suffice. The colouring can be constructed as follows. We first define a sequence of 0s and 1s recursively as follows: we start with 0 only and in each step we take the already constructed sequence, flip the 0s and 1s in it and append the resulting sequence at the end. In this way, we sequentially obtain the sequences 0, 01, 0110, 01101001, etc., which are all extensions of each other. The limiting infinite sequence is known as the Thue-Morse sequence. Another view of the sequence is that the \(i\)-th element is the parity of the number of 1s in the binary representation of \(i-1\), i.e., it is 1 if the number is odd and 0 if it is even. The colouring of integers is obtained by colouring an integer \(i\) by the difference of the \((i+1)\)-th and \(i\)-th entries in the Thue-Morse sequence, i.e., the sequence of colours will be 1, 0, -1, 1, -1, 0, 1, 0, etc. One of the properties of the Thue-Morse sequence is that it does not contain two overlapping squares, i.e., there is no sequence X such that 0X0X0 or 1X1X1 would be a subsequence of the Thue-Morse sequence. This implies that the colouring of integers that we have constructed has no two consecutive segments with the same colour pattern.

The article deals with a generalization of this notion to graphs. The nonrepetitive chromatic number of a graph \(G\) is the minimum number of colours required to colour the vertices of \(G\) so that no path with an even number of vertices is comprised of two paths with the same colour pattern. The construction presented above yields that the nonrepetitive chromatic number of every path with at least four vertices is three. The article answers in the positive the following question of Alon, Grytczuk, Hałuszczak and Riordan from 2002: Is the nonrepetitive chromatic number of planar graphs bounded? This article shows that the nonrepetitive chromatic number of every planar graph is at most 768 and provides generalizations to graphs embeddable in surfaces of higher genera and more generally to classes of graphs excluding a (topological) minor. Before their work, the best upper bound on the nonrepetitive chromatic number of planar graphs was logarithmic in the number of vertices, in addition to a universal upper bound quadratic in the maximum degree obtained using probabilistic methods. The key ingredient for the argument presented in the article is the recent powerful result by Dujmović, Joret, Micek, Morin, Ueckerdt and Wood asserting that every planar graph is a subgraph of the strong product of a path and a graph of bounded tree-width (tree-shaped graph).

The main arXiv link for this article leads to an updated version of the originally published article that bears the assigned DOI. The update concerns references in Section 3 and fixing an issue in Section 4, which contains an extension of the main result.