{"entities":{"Q1753108":{"pageid":1763850,"ns":120,"title":"Item:Q1753108","lastrevid":57533850,"modified":"2026-03-31T07:31:41Z","type":"item","id":"Q1753108","labels":{"en":{"language":"en","value":"Anagram-free graph colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873179"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$25AE5DA2-71BE-4D2D-B5F5-F64C297C193A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ef45a778e00b2ff57c5cd2315d0680feff6398d","datavalue":{"value":{"text":"Anagram-free graph colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1753108$33BCE755-DA9D-4F34-A6B3-511B7AFA8F0E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50d3dea078192d6249e9e5176ebf804b0d878bbd","datavalue":{"value":"1390.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753108$050DD451-20FC-403A-8A66-7C3C149C7B10","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"623b96c6c0e7b40512d6a1917b9f727dea13a96d","datavalue":{"value":{"entity-type":"item","numeric-id":1753107,"id":"Q1753107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$47C3C603-D8DB-41A2-BFCC-652711D50750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"88de6ea3aec65de7fd5bea5219c0d3561ce4c989","datavalue":{"value":{"entity-type":"item","numeric-id":259169,"id":"Q259169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$87D0CD05-9C9E-40C1-8364-CE37C912707C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$572E1728-FFAE-4B94-9594-4A752BEF3B6C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1753108$EB6BC237-CA5C-48BE-978A-CB8EDF8F378A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b5cfd4a4fcc42b91aa4336b36266eb2c40fc4434","datavalue":{"value":"https://arxiv.org/abs/1607.01117","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753108$9DE9BD2A-226D-4D2D-B766-CA47AFE8CE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"76d99eca5d2cf3126a087140f5c752963c8e3e71","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p20","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753108$8065FB77-F42D-4B0F-BD41-3087F1A945F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab63767f7ac138eec4a4c410f6e9ee36efbebca4","datavalue":{"value":"Summary: An anagram is a word of the form \\(WP\\) where \\(W\\) is a non-empty word and \\(P\\) is a permutation of \\(W\\). We study anagram-free graph colouring and give bounds on the chromatic number. \\textit{N. Alon} et al. [Random Struct. Algorithms 21, No. 3--4, 336--346 (2002; Zbl 1018.05032)] asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and \\(k\\)-anagram-free colouring.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753108$CD03102D-7AF8-4B68-80CB-0A3729E1F4A9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753108$F59AD600-5644-4BEE-B917-58CE4730445F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"19a00c521433b67efe0a657ec56e7665d7a2288e","datavalue":{"value":"6873179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753108$4BEE6BFA-5960-4BA7-A8BA-1446B7E4D2A2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e27858e32eac15e27b6e43f24831f3519d8ea171","datavalue":{"value":"anagram-free chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753108$4E58ABA1-4D07-445D-8485-26F2E99B33B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f980f344d19824477137154754480a89a364688e","datavalue":{"value":"abelian square-free sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753108$16110749-6C66-4481-B740-722FEDCE663E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$0FEA0F19-75E6-4482-9D9A-D291DC73D665","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d1f512d1fe4eea0e69f5e76e13f17f382480d35","datavalue":{"value":{"entity-type":"item","numeric-id":4798171,"id":"Q4798171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$983B1CC7-3640-4185-BA16-0B75BC533DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cf94a7189743cb841ea959d5d5d885063b6799f","datavalue":{"value":{"entity-type":"item","numeric-id":864157,"id":"Q864157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$A6D3D01D-A90F-4181-B6C1-966B634E1CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e09c50fe16498817b1e4ec73149dcb9591e2eff3","datavalue":{"value":{"entity-type":"item","numeric-id":5751950,"id":"Q5751950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$4A93B452-FF33-4F19-B8D3-3E39340989F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2ae5ace97b1cf5238f7b0409a56bf22bd0ffbf9","datavalue":{"value":{"entity-type":"item","numeric-id":5284660,"id":"Q5284660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$502D5ABB-049B-4A4D-AE31-CE67F77271C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c72eacd4b9652ca08435d60e1e30b6ebd0e73ec","datavalue":{"value":{"entity-type":"item","numeric-id":1856341,"id":"Q1856341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$4F70CA70-8F03-4B9B-9B02-5FCD11402999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6142cdda8c55cc1c9e145fb5621b39228a96b63c","datavalue":{"value":{"entity-type":"item","numeric-id":1141145,"id":"Q1141145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$FA3FB871-B3BA-4011-A2E9-09D6438DB8A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7cb4580046e41e82474f129797f73e3c0a82f30","datavalue":{"value":{"entity-type":"item","numeric-id":524188,"id":"Q524188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$BA0CF087-F637-40DF-B2C7-E27BC94A16FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3e3022926a23219a8c2d758707cd167f4e9174","datavalue":{"value":{"entity-type":"item","numeric-id":3159375,"id":"Q3159375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$6625C9AC-4A4E-4525-BB88-0ACA5C5F7097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97df4ee664419d4f8b9911b577e433f34391ccc3","datavalue":{"value":{"entity-type":"item","numeric-id":504976,"id":"Q504976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$4C7C0BC6-88C2-449F-9D15-7C23FA38ECF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83bf4b968c060ac2845515f449f11aad5bf60498","datavalue":{"value":{"entity-type":"item","numeric-id":925326,"id":"Q925326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$50F857D1-CDF2-4CB7-AE85-1F6B8E4D9272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bed42d2c83b7641fb6c8edf2d04e229c7cf19c8","datavalue":{"value":{"entity-type":"item","numeric-id":3424780,"id":"Q3424780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$9A7A77A8-A579-47D4-9228-261EDF6AD9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aa71240eb33813f154bb4436730d5594fac8914","datavalue":{"value":{"entity-type":"item","numeric-id":4909201,"id":"Q4909201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$A87A669A-0D6D-4449-9B1D-71FB8CA5A945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3daadd0152c177547e92aa1b696320272b14f631","datavalue":{"value":{"entity-type":"item","numeric-id":658062,"id":"Q658062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$7BB4F928-FF77-4EF1-A1D0-73367F0B0152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cec4ca6986b94348d100312ecd9c2fa93da21c7","datavalue":{"value":{"entity-type":"item","numeric-id":1689991,"id":"Q1689991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$1A420A11-4A8B-4F96-A0D7-47A8AB8D5674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a971470fccd454eb1931b81129ae986017c1dbbd","datavalue":{"value":{"entity-type":"item","numeric-id":5204304,"id":"Q5204304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$8426742E-6754-42E4-9B43-B15401E7D325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ab737df039b450a732d74f908f4ae692971a3ae","datavalue":{"value":{"entity-type":"item","numeric-id":837181,"id":"Q837181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$C995E022-A17C-4953-9EF7-1A0C8956A3DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1126028165ed25aec0b23ea9dd66a35457a4e03a","datavalue":{"value":{"entity-type":"item","numeric-id":419416,"id":"Q419416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$560C0A6C-4257-453D-A1F2-B2793E7B9AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c578b5f760e68d051acfbfe300e7f9cd3809cc2a","datavalue":{"value":{"entity-type":"item","numeric-id":2380226,"id":"Q2380226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$DDFFCE08-7CB3-462B-87BC-EADCFC9C5EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d825095afe6e2215dbc5ab36153017eec07800e3","datavalue":{"value":{"entity-type":"item","numeric-id":4344108,"id":"Q4344108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$8C393305-9C73-4455-A699-429082A71F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ffdff295e2921b9e9e97878865544e7a46699ad","datavalue":{"value":{"entity-type":"item","numeric-id":4652929,"id":"Q4652929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753108$940BD10D-9D0A-4B39-9559-51E0567BEBB3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"cede61193fa4983eb3ea24563bcc964de160cb81","datavalue":{"value":"bafkreifgkzhgg4swksddstm4kfrpgfqv7o26grttmxfwqbsubm7pzuvx2m","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753108$05CDFBF2-95F6-45B1-BD20-86FFAB6651F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce07a134df8fd5af6ef78753c37990154a70624","datavalue":{"value":{"entity-type":"item","numeric-id":3177364,"id":"Q3177364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b465684b787d33216b0f4240bb49f15484d0736","datavalue":{"value":{"amount":"+0.9258702397346495","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753108$AF028F0D-6FD6-4A95-83B6-2D676D712B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a252e1119a465a4811748844ae07e4cf4d9ba3e","datavalue":{"value":{"entity-type":"item","numeric-id":1689991,"id":"Q1689991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01615ce4dff691685278a36f5ab9391f233636b4","datavalue":{"value":{"amount":"+0.911657452583313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753108$4B5EE7BD-2039-46CE-8CAE-9044769C1282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17a416e9cc7f56818dae9fd2b397eca3e2776b15","datavalue":{"value":{"entity-type":"item","numeric-id":4684464,"id":"Q4684464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4171f01686d16a3604c888be65871c10026a5cc5","datavalue":{"value":{"amount":"+0.8912304043769836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753108$49E6A51C-1ED9-4A53-9B82-D48276FF2519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"991d771907ac649877a457d78e798c09492b5098","datavalue":{"value":{"entity-type":"item","numeric-id":2170797,"id":"Q2170797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89a6aaa3387608e38040505647d52c86500ee870","datavalue":{"value":{"amount":"+0.8363838791847229","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753108$6E677065-5E13-459F-A82D-57049061B68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8da561d4f165761031ac36995f9c8c90d9c51945","datavalue":{"value":{"entity-type":"item","numeric-id":1627156,"id":"Q1627156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4c0cb4e0e69549f9b36604edc8d8a0e97ade603","datavalue":{"value":{"amount":"+0.8356462121009827","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753108$9E723075-81BE-4189-B417-B5512B9E7CF3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1753108","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1753108"}}}}}