{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:13Z","timestamp":1780743673561,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T00:00:00Z","timestamp":1723248000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T00:00:00Z","timestamp":1723248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002869","name":"Christian-Albrechts-Universit\u00e4t zu Kiel","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002869","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Word-representable graphs were introduced in 2008 by Kitaev and Pyatkin in the context of semigroup theory. Graphs are called word-representable if there exists a word with the graph\u2019s nodes as letters such that the letters in the word alternate iff there is an edge between them in the graph. Until today numerous works investigated the word-representability of graphs but mostly from the graph perspective. In this work, we change the perspective to the words, i.e., we take classes of words and investigate the represented graphs. Our first subject of interest are the conjugates of words: we determine exactly which graphs are represented if we rotate the word. Afterwards, we look at <jats:italic>k<\/jats:italic>-local words introduced by Day et al. (FSTTCS LIPIcs, 2017) in order to gain more insights into this class of words. Here, we investigate especially which graphs are represented by 1-local words. Lastly, we prove that the language of all words representing a graph is regular. We were also able to characterise <jats:italic>k<\/jats:italic>-representable graphs, solving an open problem.\n<\/jats:p>","DOI":"10.1007\/s00236-024-00462-y","type":"journal-article","created":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T11:02:12Z","timestamp":1723287732000},"page":"383-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Word-representable graphs from a word\u2019s perspective"],"prefix":"10.1007","volume":"61","author":[{"given":"Pamela","family":"Fleischmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lukas","family":"Haschke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"L\u00f6ck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Nowotka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,10]]},"reference":[{"key":"462_CR1","doi-asserted-by":"publisher","unstructured":"Casel, K., Day, J.D., Fleischmann, P., Kociumaka, T., Manea, F., Schmid, M.L.: Graph and string parameters: connections between pathwidth, cutwidth and the locality number. In: ICALP. LIPIcs, vol. 132, 109\u2013116 (2019). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2019.109","DOI":"10.4230\/LIPICS.ICALP.2019.109"},{"issue":"13","key":"462_CR2","first-page":"3066","volume":"14","author":"S Chandrasekaran","year":"2019","unstructured":"Chandrasekaran, S., Sulthana, A.: $$k$$-Power domination of crown graph. IJAER 14(13), 3066\u20133068 (2019)","journal-title":"IJAER"},{"key":"462_CR3","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2019.v10.n3.a3","author":"G-S Cheon","year":"2019","unstructured":"Cheon, G.-S., Kim, J., Kim, M., Kitaev, S., Pyatkin, A.: On $$k$$-$$11$$-representable graphs. J. Comb. (2019). https:\/\/doi.org\/10.4310\/JOC.2019.v10.n3.a3","journal-title":"J. Comb."},{"issue":"4","key":"462_CR4","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s10878-018-0358-7","volume":"37","author":"I Choi","year":"2018","unstructured":"Choi, I., Kim, J., Kim, M.: On operations preserving semi-transitive orientability of graphs. J. Comb. Optim. 37(4), 1351\u20131366 (2018). https:\/\/doi.org\/10.1007\/s10878-018-0358-7","journal-title":"J. Comb. Optim."},{"key":"462_CR5","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.dam.2014.10.024","volume":"216","author":"A Collins","year":"2017","unstructured":"Collins, A., Kitaev, S., Lozin, V.V.: New results on word-representable graphs. Discret. Appl. Math. 216, 136\u2013141 (2017). https:\/\/doi.org\/10.1016\/j.dam.2014.10.024","journal-title":"Discret. Appl. Math."},{"key":"462_CR6","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings (2007)","DOI":"10.1017\/CBO9780511546853"},{"key":"462_CR7","doi-asserted-by":"publisher","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: FSTTCS. LIPIcs, vol. 93, pp. 24\u201312414 (2017). https:\/\/doi.org\/10.4230\/LIPICS.FSTTCS.2017.24","DOI":"10.4230\/LIPICS.FSTTCS.2017.24"},{"key":"462_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/J.ENDM.2019.02.001","volume":"71","author":"JA Enright","year":"2019","unstructured":"Enright, J.A., Kitaev, S.: Polygon-circle and word-representable graphs. Electron. Notes Discret. Math. 71, 3\u20138 (2019). https:\/\/doi.org\/10.1016\/J.ENDM.2019.02.001","journal-title":"Electron. Notes Discret. Math."},{"key":"462_CR9","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-030-67731-2_9","volume":"12607","author":"P Fleischmann","year":"2021","unstructured":"Fleischmann, P., Haschke, L., Manea, F., Nowotka, D., Tsida, C.T., Wiedenbeck, J.: Blocksequences of k-local words. SOFSEM. LNCS 12607, 119\u2013134 (2021). https:\/\/doi.org\/10.1007\/978-3-030-67731-2_9","journal-title":"SOFSEM. LNCS"},{"key":"462_CR10","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/J.DAM.2020.03.063","volume":"284","author":"M Gaetz","year":"2020","unstructured":"Gaetz, M., Ji, C.: Enumeration and extensions of word-representants. Discret. Appl. Math. 284, 423\u2013433 (2020). https:\/\/doi.org\/10.1016\/J.DAM.2020.03.063","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"462_CR11","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1515\/puma-2015-0032","volume":"28","author":"ME Glen","year":"2016","unstructured":"Glen, M.E.: Colourability and word-representability of near-triangulations. Pure Math. Appl. 28(1), 70\u201376 (2016). https:\/\/doi.org\/10.1515\/puma-2015-0032","journal-title":"Pure Math. Appl."},{"key":"462_CR12","doi-asserted-by":"publisher","unstructured":"Halld\u00f3rsson, M.M., Kitaev, S., Pyatkin, A.: Alternation graphs. In: Graph-Theoretic Concepts in Computer Science, pp. 191\u2013202 (2011). https:\/\/doi.org\/10.1007\/978-3-642-25870-1_18","DOI":"10.1007\/978-3-642-25870-1_18"},{"key":"462_CR13","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-642-14455-4_41","volume":"6224","author":"MM Halld\u00f3rsson","year":"2010","unstructured":"Halld\u00f3rsson, M.M., Kitaev, S., Pyatkin, A.V.: Graphs capturing alternations in words. DLT. LNCS 6224, 436\u2013437 (2010). https:\/\/doi.org\/10.1007\/978-3-642-14455-4_41","journal-title":"DLT. LNCS"},{"key":"462_CR14","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.dam.2015.07.033","volume":"201","author":"MM Halld\u00f3rsson","year":"2016","unstructured":"Halld\u00f3rsson, M.M., Kitaev, S., Pyatkin, A.: Semi-transitive orientations and word-representable graphs. Discrete Appl. Math. 201, 164\u2013171 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"462_CR15","doi-asserted-by":"publisher","first-page":"2","DOI":"10.37236\/4946","volume":"22","author":"ME Jones","year":"2015","unstructured":"Jones, M.E., Kitaev, S., Pyatkin, A.V., Remmel, J.B.: Representing graphs via pattern avoiding words. Electron. J. Comb. 22(2), 2 (2015). https:\/\/doi.org\/10.37236\/4946","journal-title":"Electron. J. Comb."},{"key":"462_CR16","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-031-33264-7_13","volume":"13911","author":"BG Kenkireth","year":"2023","unstructured":"Kenkireth, B.G., Malhotra, A.S.: On word-representable and multi-word-representable graphs. DLT. LNCS 13911, 156\u2013167 (2023). https:\/\/doi.org\/10.1007\/978-3-031-33264-7_13","journal-title":"DLT. LNCS"},{"key":"462_CR17","doi-asserted-by":"publisher","unstructured":"Kitaev, S., Lozin, V.V.: Words and graphs. In: Monographs in Theoretical Computer Science. An EATCS Series (2015). https:\/\/doi.org\/10.1007\/978-3-319-25859-1","DOI":"10.1007\/978-3-319-25859-1"},{"key":"462_CR18","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-319-62809-7_2","volume":"10396","author":"S Kitaev","year":"2017","unstructured":"Kitaev, S.: A comprehensive introduction to the theory of word-representable graphs. DLT. LNCS 10396, 36\u201367 (2017). https:\/\/doi.org\/10.1007\/978-3-319-62809-7_2","journal-title":"DLT. LNCS"},{"issue":"3","key":"462_CR19","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1002\/jgt.22097","volume":"85","author":"S Kitaev","year":"2017","unstructured":"Kitaev, S.: Existence of $$u$$-representation of graphs. J. Graph Theory 85(3), 661\u2013668 (2017). https:\/\/doi.org\/10.1002\/jgt.22097","journal-title":"J. Graph Theory"},{"issue":"1","key":"462_CR20","doi-asserted-by":"publisher","first-page":"45","DOI":"10.25596\/jalc-2008-045","volume":"13","author":"S Kitaev","year":"2008","unstructured":"Kitaev, S., Pyatkin, A.V.: On representable graphs. J. Autom. Lang. Comb. 13(1), 45\u201354 (2008). https:\/\/doi.org\/10.25596\/jalc-2008-045","journal-title":"J. Autom. Lang. Comb."},{"key":"462_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2023.106435","volume":"184","author":"S Kitaev","year":"2024","unstructured":"Kitaev, S., Pyatkin, A.: On semi-transitive orientability of split graphs. Inf. Process. Lett. 184, 106435 (2024). https:\/\/doi.org\/10.1016\/J.IPL.2023.106435","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"462_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s11083-008-9083-7","volume":"25","author":"S Kitaev","year":"2008","unstructured":"Kitaev, S., Seif, S.: Word problem of the Perkins semigroup via directed acyclic graphs. Order 25(3), 177\u2013194 (2008). https:\/\/doi.org\/10.1007\/s11083-008-9083-7","journal-title":"Order"},{"key":"462_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on Words","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library, Cambridge (1997)"},{"issue":"2","key":"462_CR24","first-page":"202","volume":"77","author":"RC Lyndon","year":"1954","unstructured":"Lyndon, R.C.: On Burnside\u2019s problem. Trans. Am. Math. Soc. 77(2), 202\u2013215 (1954)","journal-title":"Trans. Am. Math. Soc."},{"key":"462_CR25","unstructured":"Oliveros, D., Torres, A.: From word-representable graphs to altered Tverberg-type theorems. CoRR: abs\/2111.10038 (2021)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00462-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-024-00462-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00462-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T11:02:51Z","timestamp":1730718171000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-024-00462-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,10]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["462"],"URL":"https:\/\/doi.org\/10.1007\/s00236-024-00462-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,10]]},"assertion":[{"value":"5 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}