Open Problem Garden

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

Open Problem Garden

Bibliography

Reply

Navigate

Recent Activity