{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:28:13Z","timestamp":1763663293751},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T00:00:00Z","timestamp":1435104000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00493-015-3070-6","type":"journal-article","created":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T09:41:58Z","timestamp":1435138918000},"page":"661-686","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Nonrepetitive colouring via entropy compression"],"prefix":"10.1007","volume":"36","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[]},{"given":"Jakub","family":"Kozik","sequence":"additional","affiliation":[]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"3070_CR1","doi-asserted-by":"crossref","unstructured":"M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. K\u00fcndgen and R. Ramamurthi: Coloring with no 2-colored P4\u2019s, Electron. J. Combin., 11 #R26, 2004.","DOI":"10.37236\/1779"},{"key":"3070_CR2","doi-asserted-by":"crossref","first-page":"1375","DOI":"10.1016\/j.disc.2007.07.063","volume":"308","author":"N Alon","year":"2008","unstructured":"N. Alon and J. Grytozuk: Breaking the rhythm on graphs, Discrete Math. 308 (2008), 1375\u20131380.","journal-title":"Discrete Math."},{"key":"3070_CR3","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1002\/rsa.10057","volume":"21","author":"N Alon","year":"2002","unstructured":"N. Alon, J. Grytcz\u00fck, M. Haluszczak and O. Riordan: Non-repetitive colorings of graphs, Random Structures Algorithms 21 (2002), 336\u2013346.","journal-title":"Random Structures Algorithms"},{"key":"3070_CR4","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1002\/jgt.21695","volume":"74","author":"J Bar\u00c1t","year":"2013","unstructured":"J. Bar\u00c1t and J. Czap: Facial nonrepetitive vertex coloring of plane graphs, J. Graph Theory 74 (2013), 115\u2013121.","journal-title":"J. Graph Theory"},{"key":"3070_CR5","first-page":"411","volume":"44","author":"J Bar\u00c1t","year":"2007","unstructured":"J. Bar\u00c1t and P. Varj\u00fa: On square-free vertex colorings of graphs, Studia Sci. Math. Hungar. 44 (2007), 411\u2013422.","journal-title":"Studia Sci. Math. Hungar."},{"key":"3070_CR6","first-page":"377","volume":"87","author":"J Bar\u00c1t","year":"2008","unstructured":"J. Bar\u00c1t and P. Varj\u00fa: On square-free edge colorings of graphs, Ars Combin. 87 (2008), 377\u2013383.","journal-title":"Ars Combin."},{"key":"3070_CR7","doi-asserted-by":"crossref","first-page":"R99","DOI":"10.37236\/823","volume":"15","author":"J Bar\u00c1t","year":"2008","unstructured":"J. Bar\u00c1t and D. R. Wood: Notes on nonrepetitive graph colouring, Electron. J. Combin. 15 (2008), R99.","journal-title":"Electron. J. Combin."},{"key":"3070_CR8","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0012-365X(79)90077-3","volume":"25","author":"O Borodin","year":"1979","unstructured":"O. Borodin: On acyclic colorings of planar graphs, Discrete Math. 25 (1979), 211\u2013236.","journal-title":"Discrete Math."},{"key":"3070_CR9","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.disc.2006.06.017","volume":"307","author":"B BreSar","year":"2007","unstructured":"B. BreSar, J. Grytczuk, S. KlavZar, S. Niwczyk and I. Pe-terin: Nonrepetitive colorings of trees, Discrete Math. 307 (2007), 163\u2013172.","journal-title":"Discrete Math."},{"key":"3070_CR10","first-page":"3","volume":"70","author":"B Bre\u0161ar","year":"2004","unstructured":"B. Bre\u0161ar and S. Klav\u017dar: Square-free colorings of graphs, Ars Combin. 70 (2004), 3\u201313.","journal-title":"Ars Combin."},{"key":"3070_CR11","doi-asserted-by":"crossref","first-page":"2132","DOI":"10.1137\/100799642","volume":"42","author":"K Chandrasekaran","year":"2013","unstructured":"K. Chandrasekaran, N. Goyal and B. Haeupler: Deterministic Algorithms for the Lov\u00e1sz Local Lemma, SIAM J. Comput. 42 (2013), 2132\u20132155.","journal-title":"SIAM J. Comput."},{"key":"3070_CR12","first-page":"469","volume":"51","author":"P Cheilaris","year":"2010","unstructured":"P. Cheilaris, E. Specker and S. Zachos: Neochromatica, Com-ment. Math. Univ. Carolin. 51 (2010), 469\u2013480.","journal-title":"Com-ment. Math. Univ. Carolin."},{"key":"3070_CR13","doi-asserted-by":"crossref","unstructured":"J. D. Currie: There are ternary circular square-free words of length n for n\u2265:18, Electron. J. Combin. 9 (2002).","DOI":"10.37236\/1671"},{"key":"3070_CR14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.tcs.2005.01.004","volume":"339","author":"J D Currie","year":"2005","unstructured":"J. D. Currie: Pattern avoidance: themes and variations, Theoret. Comput. Sci. 339 (2005), 7\u201318.","journal-title":"Theoret. Comput. Sci."},{"key":"3070_CR15","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1016\/j.endm.2007.01.063","volume":"28","author":"S Czerwi\u0143ski","year":"2007","unstructured":"S. Czerwi\u0143ski and J. Grytczuk: Nonrepetitive colorings of graphs, Electron. Notes Discrete Math. 28 (2007), 453\u2013459.","journal-title":"Electron. Notes Discrete Math."},{"key":"3070_CR16","first-page":"1112.5524","volume-title":"Nonrepetitive colouring via entropy compression","author":"V Dujmovi\u0107","year":"2011","unstructured":"V. Dujmovi\u0107, G. Joret, J. Kozik and D. R. Wood: Nonrepetitive colouring via entropy compression, 2011. arXiv: 1112.5524"},{"key":"3070_CR17","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1016\/j.ejc.2013.02.007","volume":"34","author":"L Esperet","year":"2013","unstructured":"L. Esperet and A. Parreau: Acyclic edge-coloring using entropy compression, European J. Combin. 34 (2013), 1019\u20131027.","journal-title":"European J. Combin."},{"key":"3070_CR18","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1002\/jgt.20029","volume":"47","author":"G Fertin","year":"2004","unstructured":"G. Fertin, A. Raspaud and B. Reed: Star coloring of graphs, J. Graph Theory 47 (2004), 163\u2013182.","journal-title":"J. Graph Theory"},{"key":"3070_CR19","doi-asserted-by":"crossref","first-page":"2045","DOI":"10.1016\/j.dam.2011.07.017","volume":"159","author":"F Fiorenzi","year":"2011","unstructured":"F. Fiorenzi, P. Ochem, P. O. de Mendez and X. Zhu: Thue choos-ability of trees, Discrete Applied Math. 159 (2011), 2045\u20132049.","journal-title":"Discrete Applied Math"},{"key":"3070_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"P Flajolet","year":"2009","unstructured":"P. Flajolet and R. Sedgewick: Analytic combinatorics, Cambridge University Press, 2009."},{"key":"3070_CR21","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/BF02764716","volume":"14","author":"B Gr\u00fcnbaum","year":"1973","unstructured":"B. Gr\u00fcnbaum: Acyclic colorings of planar graphs, Israel J. Math. 14 (1973), 390\u2013408.","journal-title":"Israel J. Math."},{"key":"3070_CR22","doi-asserted-by":"crossref","first-page":"R44","DOI":"10.37236\/1660","volume":"9","author":"J Grytczuk","year":"2002","unstructured":"J. Grytczuk: Thue-like sequences and rainbow arithmetic progressions, Electron. J. Combin. 9 (2002), R44.","journal-title":"Electron. J. Combin."},{"key":"3070_CR23","volume-title":"Int. J. Math. Math. Sci.","author":"J Grytczuk","year":"2007","unstructured":"J. Grytczuk: Nonrepetitive colorings of graphs\u2014a survey, Int. J. Math. Math. Sci., 74639, 2007."},{"key":"3070_CR24","first-page":"209","volume-title":"Trends in Mathematics","author":"J Grytczuk","year":"2007","unstructured":"J. Grytczuk: Nonrepetitive graph coloring, in: Graph Theory in Paris, Trends in Mathematics, 209\u2013218. Birkhauser, 2007."},{"key":"3070_CR25","doi-asserted-by":"crossref","first-page":"4419","DOI":"10.1016\/j.disc.2007.08.039","volume":"308","author":"J Grytczuk","year":"2008","unstructured":"J. Grytczuk: Thue type problems for graphs, points, and numbers, Discrete Math. 308 (2008), 4419\u20134429.","journal-title":"Discrete Math."},{"key":"3070_CR26","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1002\/rsa.20411","volume":"42","author":"J Grytczuk","year":"2013","unstructured":"J. Grytczuk, J. Kozik and P. Micek: A new approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214\u2013225.","journal-title":"Random Structures Algorithms"},{"key":"3070_CR27","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1002\/rsa.20347","volume":"38","author":"J Grytczuk","year":"2011","unstructured":"J. Grytczuk, J. Przybylo and X. Zhu: Nonrepetitive list colourings of paths, Random Structures Algorithms 38 (2011), 162\u2013173.","journal-title":"Random Structures Algorithms"},{"key":"3070_CR28","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/2049697.2049702","volume":"58","author":"B Haeupler","year":"2011","unstructured":"B. Haeupler, B. Saha and A. Srinivasan: New constructive aspects of the Lov\u00e1sz local lemma, J. ACM 58 (2011), Art. 28.","journal-title":"J. ACM"},{"key":"3070_CR29","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.disc.2011.09.027","volume":"312","author":"J Harant","year":"2012","unstructured":"J. Harant and S. Jendrol\u2019: Nonrepetitive vertex colorings of graphs, Discrete Math. 312 (2012), 374\u2013380.","journal-title":"Discrete Math."},{"key":"3070_CR30","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1002\/jgt.20488","volume":"66","author":"F Havet","year":"2011","unstructured":"F. Havet, S. Jendrol\u2019, R. Sot\u00c1k and E. \u0160krabul\u2019\u00c1kova: Facial non-repetitive edge-coloring of plane graphs, J. Graph Theory 66 (2011), 38\u201348.","journal-title":"J. Graph Theory"},{"key":"3070_CR31","first-page":"37","volume":"15","author":"S Jendrol\u2019","year":"2009","unstructured":"S. Jendrol\u2019 and E. \u0160krabul\u2019\u00c1kov\u00c1: Facial non-repetitive edge colouring of semiregular polyhedra, Acta Univ. M. Belii Ser. Math. 15 (2009), 37\u201352.","journal-title":"Acta Univ. M. Belii Ser. Math."},{"key":"3070_CR32","volume-title":"Nonrepetitive colorings of blowups of graphs","author":"B Keszegh","year":"2012","unstructured":"B. Keszegh, B. Patk\u00d3s and X. Zhu: Nonrepetitive colorings of blowups of graphs, 2012. arXiv: 1210.5607."},{"key":"3070_CR33","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/1993636.1993669","volume-title":"Proc. 43rd Annual ACM Symposium on Theory of Computing","author":"K Kolipaka","year":"2011","unstructured":"K. Kolipaka and M. Szegedy: Moser and Tardos meet Lov\u00e1sz, in: Proc. 43rd Annual ACM Symposium on Theory of Computing (STOC\u201911), 235\u2013244. ACM, 2011."},{"key":"3070_CR34","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1007\/978-3-642-32512-0_51","volume":"7408","author":"K Kolipaka","year":"2012","unstructured":"K. Kolipaka, M. Szegedy and Y. Xu: A sharper local lemma with improved applications, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, vol. 7408 of Lecture Notes in Computer Science, 603\u2013614. 2012.","journal-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"},{"key":"3070_CR35","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1137\/120866361","volume":"27","author":"J Kozik","year":"2013","unstructured":"J. Kozik and P. Micek: Nonrepetitive choice number of trees, SIAM J. Discrete Math. 27 (2013), 436\u2013446.","journal-title":"SIAM J. Discrete Math."},{"key":"3070_CR36","doi-asserted-by":"crossref","first-page":"4473","DOI":"10.1016\/j.disc.2007.08.043","volume":"308","author":"A K\u00fcndgen","year":"2008","unstructured":"A. K\u00fcndgen and M. J. Pelsmajer: Nonrepetitive colorings of graphs of bounded tree-width, Discrete Math. 308 (2008), 4473\u20134478.","journal-title":"Discrete Math."},{"key":"3070_CR37","volume-title":"The complexity of nonrepetitive edge coloring of graphs","author":"F Manin","year":"2007","unstructured":"F. Manin: The complexity of nonrepetitive edge coloring of graphs, 2007. arXiv: 0709.4497."},{"key":"3070_CR38","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.dam.2008.04.015","volume":"157","author":"D Marx","year":"2009","unstructured":"D. Marx and M. Schaefer: The complexity of nonrepetitive coloring, Discrete Appl. Math. 157 (2009), 13\u201318.","journal-title":"Discrete Appl. Math."},{"key":"3070_CR39","doi-asserted-by":"crossref","unstructured":"R. A. Moser and G. Tardos: A constructive proof of the general Lov\u00e1sz local lemma, J. ACM 57 (2010).","DOI":"10.1145\/1667053.1667060"},{"key":"3070_CR40","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/978-3-642-55566-4_29","volume":"25","author":"J Ne\u0160et\u0158il","year":"2003","unstructured":"J. Ne\u0160et\u0158il and P. O. de Mendez: Colorings and homomorphisms of minor closed classes, in: Boris Aronov, Saugata Basu, J\u00e1nos Pach, and Micha Sharir, eds., Discrete and Computational Geometry, The Goodman-Pollack Festschrift, vol. 25 of Algorithms and Combinatorics, 651\u2013664. Springer, 2003.","journal-title":"The Goodman-Pollack Festschrift"},{"key":"3070_CR41","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J Ne\u0160et\u0158il","year":"2011","unstructured":"J. Ne\u0160et\u0158il, P. O. de Mendez and D. R. Wood: Characterisations and examples of graph classes with bounded expansion, European J. Combin. 33 (2011), 350\u2013373.","journal-title":"European J. Combin."},{"key":"3070_CR42","doi-asserted-by":"crossref","unstructured":"P. Ochem and A. Pinlou: Application of entropy compression in pattern avoidance, 2013. Electronic Journal of Combinatorics 21 (2014).","DOI":"10.37236\/3038"},{"key":"3070_CR43","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1002\/rsa.20354","volume":"38","author":"W Pegden","year":"2011","unstructured":"W. Pegden: Highly nonrepetitive sequences: winning strategies from the local lemma, Random Structures Algorithms 38 (2011), 140\u2013161.","journal-title":"Random Structures Algorithms"},{"key":"3070_CR44","doi-asserted-by":"crossref","unstructured":"A. Pezarski and M. Zmarz: Non-repetitive 3-coloring of subdivided graphs, Electron. J. Combin. 16 (2009), N15.","DOI":"10.37236\/253"},{"key":"3070_CR45","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1002\/jgt.21781","volume":"77","author":"J Przybylo","year":"2014","unstructured":"J. Przybylo: On the facial Thue choice index via entropy compression, J. Graph Theory, 2013 77 (2014), 180\u2013189.","journal-title":"J. Graph Theory"},{"key":"3070_CR46","volume-title":"On the facial Thue choice number of plane graphs via entropy compression method","author":"J Przybylo","year":"2013","unstructured":"J. Przybylo, J. Schreyer and E. \u0160krabul\u2019\u00c1kova: On the facial Thue choice number of plane graphs via entropy compression method, 2013. arXiv: 1308.5128."},{"key":"3070_CR47","first-page":"1","volume":"7","author":"A Thue","year":"1906","unstructured":"A. Thue: \u00dcber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania 7 (1906), 1\u201322.","journal-title":"Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania"},{"key":"3070_CR48","first-page":"37","volume":"7","author":"D R Wood","year":"2005","unstructured":"D. R. Wood: Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. Theor. Comput. Sci. 7 (2005), 37\u201350.","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3070-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-015-3070-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3070-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3070-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,4]],"date-time":"2020-09-04T02:13:01Z","timestamp":1599185581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-015-3070-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,24]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["3070"],"URL":"https:\/\/doi.org\/10.1007\/s00493-015-3070-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,24]]}}}