Originators: Noga Alon and Jarek Grytczuk (presented by Douglas West - REGS 2008)
Definitions: A coloring of the vertices of a graph is nonrepetitive if there is no path along which a color pattern immediately repeats. It is k-nonrepetitive if there is no pattern that immediately repeats k times; this condition becomes weaker as k increases. Let πk(G) denote the minimum number of colors in a k-nonrepetitive coloring of G. The rhythm threshold of a family F of graphs is the minimum r such that there exists a fixed value k such that πk(G)≤r for all G∈F.
Background: Nonrepetitive colorings generalize to graphs the study of nonrepetitive words. The famous Thue-Morse word is a 3-coloring of an arbitrarily long path without repetitions. Thus π2(Pn)=3 (every 2-coloring of P4 has a repetition). It is also true that π3(Pn)=π3(Cn)=2.
Conjecture ([AG]): The rhythm threshold of the family of planar graphs is finite (perhaps it is 4).
Comments: Kündgen and Pelsmajer [KP] proved that the family of graphs with treewidth at most w has finite rhythm threshold (at most 4w). The conjecture would break new ground, since the family of planar graphs contains graphs with arbitrarily high treewidth (in particular, the treewidth of the n-by-n grid is n).
Further papers and problems about nonrepetitive colorings appear in [BGKNP,CG,G1,G2,G3]. For example, one can ask for the minimum number of colors that suffice to permit nonrepetitive colorings for all graphs in a given family. Note that every nonrepetitive coloring is a proper coloring, so this is always at least the chromatic number. Answering a question of Grytczuk, Kündgen and Pelsmajer [KP] showed that every outerplanar graph has a nonrepetitive 12-coloring.
References:
[AG] Alon, Noga; Grytczuk, Jarosław; Breaking the rhythm on graphs.
Discrete Math. 308 (2008), no. 8, 1375--1380.
[BGKNP] Brešar, B.; Grytczuk, J.; Klavžar, S.; Niwczyk, S.; Peterin,
I.; Nonrepetitive colorings of trees. Discrete Math. 307 (2007), no. 2,
163--172.
[CG] Czerwiński, Sebastian; Grytczuk, Jarek; Nonrepetitive colorings of
graphs. 6th Czech-Slovak International Symposium on Combinatorics, Graph
Theory, Algorithms and Applications, 453--459, Electron. Notes Discrete Math.,
28, Elsevier, Amsterdam, 2007.
[G1] Grytczuk, Jarosław; Nonrepetitive graph coloring. Graph theory in Paris,
209--218, Trends Math., Birkhäuser, Basel, 2007.
[G2] Grytczuk, Jarosław; Pattern avoidance on graphs.
Discrete Math. 307 (2007), no. 11-12, 1341--1346.
[G3] Grytczuk, Jarosław; Nonrepetitive colorings of graphs---a survey.
Int. J. Math. Math. Sci. 2007, Art. ID 74639, 10 pp.
[KP] Kündgen, André; Pelsmajer, Michael;
Nonrepetitive colorings of graphs of bounded tree-width.
Discrete Math. (2008), Special issue in honor of Miklós Simonovits.