{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:12Z","timestamp":1787323392126,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>An anagram is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. A vertex coloring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph coloring was independently introduced by Kam\u010dev, \u0141uczak, and Sudakov [ Combin. Probab. Comput., 27 (2018), pp. 623--642] and ourselves [ Electron. J. Combin., 25 (2018), pp. 2--20]. In this paper we introduce the study of anagram-free colorings of graph subdivisions. We show that every graph has an anagram-free 8-colorable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free $10$-colorable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.<\/jats:p>","DOI":"10.1137\/17m1145574","type":"journal-article","created":{"date-parts":[[2018,9,27]],"date-time":"2018-09-27T10:05:25Z","timestamp":1538042725000},"page":"2346-2360","source":"Crossref","is-referenced-by-count":0,"title":["Anagram-Free Colorings of Graph Subdivisions"],"prefix":"10.1137","volume":"32","author":[{"given":"Tim E.","family":"Wilson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8866-3041","authenticated-orcid":true,"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,9,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10057"},{"key":"atypb2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/823","volume":"15","author":"Bar\u00e1t J.","year":"2008","journal-title":"Electron. J. Combin."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.06.017"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1086\/406830"},{"key":"atypb5","first-page":"259","volume":"14","author":"Cummings L. J.","year":"1996","journal-title":"Australas. J. Combin."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3070-6"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J. Grytczuk,\n                      Nonrepetitive colorings of graphs a survey\n                      , Int. J. Math. Math. Sci. (2007), Art. ID 74639.","DOI":"10.1155\/2007\/74639"},{"key":"atypb8","first-page":"209","author":"Grytczuk J.","year":"2007","journal-title":"Basel"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20411"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.09.027"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831700027X"},{"key":"atypb12","first-page":"41","author":"Ker\u00e4nen V.","year":"1992","journal-title":"Berlin"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.027"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.008"},{"key":"atypb15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/253","volume":"16","author":"Pezarski A.","year":"2009","journal-title":"Electron. J. Combin."},{"key":"atypb16","unstructured":"A. Thue,\n                      Probleme \u00fcber ver\u00e4nderungen von zeichenreihen nach gegebenen regeln\n                      , I. Math. naturv. Klasse, 10. Christiana Videnskabs-Selskabs Skrifte, 1914."},{"key":"atypb17","doi-asserted-by":"crossref","first-page":"2","DOI":"10.37236\/6267","volume":"25","author":"Wilson T. E.","year":"2018","journal-title":"Electron. J. Combin."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1145574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:44Z","timestamp":1787320784000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1145574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1145574"],"URL":"https:\/\/doi.org\/10.1137\/17m1145574","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}