×

Nonrepetitive colorings of graphs – a survey. (English) Zbl 1139.05020

Summary: A vertex coloring \(f\) of a graph \(G\) is nonrepetitive if there are no integer \(r\geq 1\) and a simple path \(\nu_1,\dots,\nu_{2r}\) in \(G\) such that \(f(\nu_i)= f(\nu_{r+i})\) for all \(i=1,\dots,r\). This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveys problems and results on this topic.

MSC:

05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] A. Thue, “Über unendliche Zeichenreichen,” Norske Videnskabers Selskabs Skrifter, I Mathematisch-Naturwissenschaftliche Klasse, Christiania, vol. 7, pp. 1-22, 1906. · JFM 37.0066.17
[2] J.-P. Allouche and J. Shallit, Automatic Sequences. Theory, Applications, Generalizations, Cambridge University Press, Cambridge, UK, 2003. · Zbl 1086.11015
[3] J. Berstel, Axel Thue’s Papers on Repetitions in Words: A Translation, vol. 20 of Publications du LaCIM, Université du Québec a Montréal, Montreal, Quebec, Canada, 1995.
[4] J. Berstel, “Axel Thue’s work on repetitions in words,” in Séries Formelles et Combinatoire Algébrique, P. Leroux and C. Reutenauer, Eds., Publications du LaCIM, pp. 65-80, Université du Québec a Montréal, Montreal, Quebec, Canada, 1992.
[5] M. Lothaire, Combinatorics on Words, vol. 17 of Encyclopedia of Mathematics and Its Applications, Addison-Wesley, Reading, Mass, USA, 1983. · Zbl 0514.20045
[6] M. Lothaire, Algebraic Combinatorics on Words, vol. 90 of Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, UK, 2002. · Zbl 1001.68093
[7] R. O. Shelton, “Aperiodic words on three symbols,” Journal für die Reine und Angewandte Mathematik, vol. 321, pp. 195-209, 1981. · Zbl 0441.05007
[8] R. O. Shelton, “Aperiodic words on three symbols. II,” Journal für die Reine und Angewandte Mathematik, vol. 327, pp. 1-11, 1981. · Zbl 0455.05014
[9] R. O. Shelton and R. P. Soni, “Aperiodic words on three symbols. III,” Journal für die Reine und Angewandte Mathematik, vol. 330, pp. 44-52, 1982. · Zbl 0467.05010
[10] N. Alon and J. H. Spencer, The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, NY, USA, 2nd edition, 2000. · Zbl 0996.05001
[11] J. Beck, “An application of Lovász local lemma: there exists an infinite 01-sequence containing no near identical intervals,” in Finite and Infinite Sets, Vol. I, II (Eger, 1981), vol. 37 of Colloquia Mathematica Societatis János Bolyai, pp. 103-107, North-Holland, Amsterdam, The Netherlands, 1984. · Zbl 0567.05010
[12] J. D. Currie, “Pattern avoidance: themes and variations,” Theoretical Computer Science, vol. 339, no. 1, pp. 7-18, 2005. · Zbl 1076.68051
[13] J. Grytczuk, “Thue-like sequences and rainbow arithmetic progressions,” Electronic Journal of Combinatorics, vol. 9, no. 1, R44, pp. 1-10, 2002. · Zbl 1035.05094
[14] J. D. Currie, “There are ternary circular square-free words of length n for n\geq 18,” Electronic Journal of Combinatorics, vol. 9, no. 1, N10, pp. 1-7, 2002. · Zbl 1057.68081
[15] N. Alon, J. Grytczuk, M. Hałuszczak, and O. Riordan, “Nonrepetitive colorings of graphs,” Random Structures and Algorithms, vol. 21, no. 3-4, pp. 336-346, 2002. · Zbl 1018.05032
[16] A. Kündgen and M. J. Pelsmajer, “Nonrepetitive colorings of graphs of bounded treewidth,” preprint, 2003. · Zbl 1154.05033
[17] J. Barát and P. P. Varjú, “On square-free vertex colorings of graphs,” to appear in Studia Scientiarum Mathematicarum Hungarica. · Zbl 1164.05021
[18] J. Grytczuk, “Nonrepetitive graph coloring,” in Graph Theory, Trends in Mathematics, pp. 209-218, Birkhäuser, Boston, Mass, USA, 2006. · Zbl 1120.05029
[19] H. A. Kierstead and D. Yang, “Orderings on graphs and game coloring number,” Order, vol. 20, no. 3, pp. 255-264, 2003. · Zbl 1041.05029
[20] J. Ne\vset\vril and P. Ossona de Mendez, “Tree-depth, subgraph coloring and homomorphism bounds,” European Journal of Combinatorics, vol. 27, no. 6, pp. 1022-1041, 2006. · Zbl 1089.05025
[21] J. Barát and D. Wood, “Notes on nonrepetitive graph colouring,” preprint, 2005, http://arxiv.org/abs/math.CO/0509608. · Zbl 1163.05316
[22] B. Bre\vsar, J. Grytczuk, S. Klav\vzar, S. Niwczyk, and I. Peterin, “Nonrepetitive colorings of trees,” Discrete Mathematics, vol. 307, no. 2, pp. 163-172, 2007. · Zbl 1106.68089
[23] A. Thue, “Über die gegenseitigen Lage gleicher Teile gewisser Zeichenreihen,” Norske Videnskabers Selskabs Skrifter, I Mathematisch-Naturwissenschaftliche Klasse, Christiania, vol. 1, pp. 1-67, 1912. · JFM 44.0462.01
[24] J. D. Currie and D. S. Fitzpatrick, “Circular words avoiding patterns,” in Developments in Language Theory, vol. 2450 of Lecture Notes in Comput. Sci., pp. 319-325, Springer, Berlin, Germany, 2003. · Zbl 1015.68137
[25] N. Alon and J. Grytczuk, “Breaking the rhythm on graphs,” to appear in Discrete Mathematics. · Zbl 1135.05018
[26] K. A. Berman and J. L. Paul, “A 4-color theorem for surfaces of genus g,” Proceedings of the American Mathematical Society, vol. 105, no. 2, pp. 513-522, 1989. · Zbl 0672.05028
[27] E. Sopena, “Oriented graph coloring,” Discrete Mathematics, vol. 229, no. 1-3, pp. 359-369, 2001. · Zbl 0971.05039
[28] O. V. Borodin, “On acyclic colorings of planar graphs,” Discrete Mathematics, vol. 25, no. 3, pp. 211-236, 1979. · Zbl 0406.05031
[29] N. Alon and T. H. Marshall, “Homomorphisms of edge-colored graphs and Coxeter groups,” Journal of Algebraic Combinatorics, vol. 8, no. 1, pp. 5-13, 1998. · Zbl 0911.05034
[30] B. Bre\vsar and S. Klav\vzar, “Square-free colorings of graphs,” Ars Combinatoria, vol. 70, pp. 3-13, 2004. · Zbl 1093.05023
[31] J. Barát and P. P. Varjú, “On square-free edge colorings of graphs,” to appear in Ars Combinatoria. · Zbl 1164.05021
[32] J. D. Currie, “Which graphs allow infinite nonrepetitive walks?” Discrete Mathematics, vol. 87, no. 3, pp. 249-260, 1991. · Zbl 0718.05030
[33] J. Grytczuk and W. Śliwa, “Nonrepetitive colorings of infinite sets,” Discrete Mathematics, vol. 265, no. 1-3, pp. 365-373, 2003. · Zbl 1030.68069
[34] D. R. Bean, A. Ehrenfeucht, and G. F. McNulty, “Avoidable patterns in strings of symbols,” Pacific Journal of Mathematics, vol. 85, no. 2, pp. 261-294, 1979. · Zbl 0428.05001
[35] J. D. Currie and J. Simpson, “Non-repetitive tilings,” Electronic Journal of Combinatorics, vol. 9, no. 1, R28, pp. 1-13, 2002. · Zbl 1004.05020
[36] J. D. Currie and C. W. Pierce, “The fixing block method in combinatorics on words,” Combinatorica, vol. 23, no. 4, pp. 571-584, 2003. · Zbl 1099.68684
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.