Planar graphs have bounded nonrepetitive chromatic number

Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

A colouring of a graph is nonrepetitive if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. We show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Hałuszczak and Riordan (2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor.

Original languageEnglish
Article number5
Number of pages11
JournalAdvances in Combinatorics
Volume2020
Issue number1
DOIs
Publication statusPublished - 1 Jan 2020

Cite this