# Nonrepetitive colourings of planar graphs

**Question**Do planar graphs have bounded nonrepetitive chromatic number?

A path in a vertex-coloured graph is *repetitively coloured* if and receive the same colour for . A colouring of is *nonrepetitive* if no path is repetitively coloured. The *nonrepetitive chromatic number* of a graph is the minimum number of colours in a nonrepetitive colouring of .

For example, every path is nonrepetitively 3-colourable [T], every tree is nonrepetitively 4-colourable [BGKNP], every outerplanar graphs is nonrepetitively 12-colourable [KP], every graph of treewidth is nonrepetitively -colourable [KP], and every graph of maximum degree is colourable [AGHR,DJKW].

The best known upper bound on the nonrepetitive chromatic number of -vertex planar graphs is [DFJW]. The best lower bound is 11, due to Pascal Ochem [DFJW].

More generally, it is open whether graphs with bounded genus or graphs in a fixed minor-closed class have bounded nonrepetitive chromatic number. For such graphs classes, a upper bound is known [DMW].

## Bibliography

*[AGHR] Noga Alon, Jarosław Grytczuk, Mariusz Hałuszczak, Oliver Riordan. Nonrepetitive colorings of graphs. Random Structures Algorithms, 21(3-4):336–346, 2002. MathSciNet.

[BGKNP] B. Brešar, J. Grytczuk, S. Klavžar, S. Niwczyk, I. Peterin. Nonrepetitive colorings of trees. Discrete Math., 307(2):163–172, 2007. MathSciNet.

[DFJW] V. Dujmović, F. Frati, G. Joret, D. R. Wood. Nonrepetitive colourings of planar graphs with colours, Electronic J. Combinatorics 20.1:P51, 2013.

[DJKW] V. Dujmović, G. Joret, J. Kozik, D. R. Wood. Nonrepetitive colouring via entropy compression, Combinatorica, to appear.

[DMW] V. Dujmović, P. Morin, D. R. Wood. Layered separators in minor-closed families with applications, 2014. arXiv:1306.1595

[KP] André Kündgen, Michael Pelsmajer. Nonrepetitive colorings of graphs of bounded tree-width. Discrete Math., 308(19):4473–4478, 2008.

[T] Axel Thue. Uber unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7:1-22, 1906.

* indicates original appearance(s) of problem.