Planar graphs have bounded nonrepetitive chromatic number
arXiv:1904.05269 · doi:10.19086/aic.12100
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, Haluszczak 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.
References in corpus (9)
- Layout of Graphs with Bounded Tree-Width
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Nonrepetitive Colouring via Entropy Compression
- Layered Separators in Minor-Closed Graph Classes with Applications
- On the facial Thue choice index via entropy compression
- Vertex coloring of plane graphs with nonrepetitive boundary paths
- Nonrepetitive Colourings of Planar Graphs with Colours
- Pathwidth and nonrepetitive list coloring
- Nonrepetitive edge-colorings of trees