Nonrepetitive colorings of graphs

Graphs, Hypergraphs, and Computing

04 March 15:30 - 16:30

Jaroslaw Grytczuk - Jagiellonian University

A colored path P is repetitive if the sequence of colors on the first half of P is the same as the sequence of colors on the second half of P. A coloring of a graph G is nonrepetitive if there is no repetitive path in G.

This notion was introduced in 2002 as a graph theoretic variation on the theorem of Thue on words without repetitions. A major open problem in this area is whether planar graphs are nonrepetitively colorable with a bounded number of colors. I will present some recent results towards resolution of this question. Particularly promising seems to be a newly developed approach, called entropy compression, that appears to be useful also for other types of graph colorings.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to