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
Adam Mickiewicz University
Technical University of Denmark, DTU