Home » Subject » Graph Theory » Coloring » Vertex coloring

Nonrepetitive colourings of planar graphs (Solved)

Importance: Medium ✭✭
Author(s): Alon N.
Grytczuk J.
Hałuszczak M.
Riordan O.
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: nonrepetitive colouring
planar graphs
Recomm. for undergrads: no
Posted by: David Wood
on: March 24th, 2014
Solved by: Planar graphs have bounded nonrepetitive chromatic number Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood https://arxiv.org/abs/1904.05269
Question   Do planar graphs have bounded nonrepetitive chromatic number?

A path $ (v_1,v_2,\dots,v_{2t}) $ in a vertex-coloured graph $ G $ is repetitively coloured if $ v_i $ and $ v_{t+i} $ receive the same colour for $ 1\leq i\leq t $. A colouring of $ G $ is nonrepetitive if no path is repetitively coloured. The nonrepetitive chromatic number of a graph $ G $ is the minimum number of colours in a nonrepetitive colouring of $ G $.

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 $ k $ is nonrepetitively $ 4^k $-colourable [KP], and every graph of maximum degree $ \Delta $ is $ O(\Delta^2) $ colourable [AGHR,DJKW].

The best known upper bound on the nonrepetitive chromatic number of $ n $-vertex planar graphs is $ O(\log n) $ [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 $ O(\log n) $ upper bound is known [DMW].

Update [2019]: This problem has been solved [DEJWW]. The authors prove that every planar graph is nonrepetitively 768-colourable. More generally, they prove that graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor have bounded nonrepetitive chromatic number.

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 $ O(\log n) $ 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 graph classes with applications. J. Combinatorial Theory Series B 127:111–147, 2017.

[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.

[DEJWW] Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood. Planar graphs have bounded nonrepetitive chromatic number, 2019.


* indicates original appearance(s) of problem.
add new comment