{"entities":{"Q941387":{"pageid":943235,"ns":120,"title":"Item:Q941387","lastrevid":65575722,"modified":"2026-04-12T03:33:02Z","type":"item","id":"Q941387","labels":{"en":{"language":"en","value":"Nonrepetitive colorings of graphs of bounded tree-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5321319"}},"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":"Q941387$A2A5EC51-D106-444E-B3BE-02E3BC13F5DE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"94be43973daf00b5aaaf73b5fab364363e586a87","datavalue":{"value":{"text":"Nonrepetitive colorings of graphs of bounded tree-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q941387$7103F354-9781-400F-A93D-FA72F2E1142A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e075e88f06db827bf66dc8e4b28fb9aa0bd506fe","datavalue":{"value":"1154.05033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941387$73A0CAE8-5CEF-4E02-B2B3-E2CBA8D9E9A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98f6744a70be4a22c5bb31429ae0ebafcb6d1056","datavalue":{"value":{"entity-type":"item","numeric-id":171753,"id":"Q171753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$55B8565D-48DF-437D-AB1D-29370A6CA4D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dccc1bbd4495a1169607841bd43f44872a74f964","datavalue":{"value":{"entity-type":"item","numeric-id":396917,"id":"Q396917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$4340B047-33C5-40EC-AE21-2978152DFB04","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$B764D868-4D8D-4935-9F35-50AC513154A9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2bf0f0ee9c49018dff9c641c5da1a78a5da873e5","datavalue":{"value":{"time":"+2008-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q941387$ABBF85A7-DBA9-4AC8-ABB7-BA7CC6BF01AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"579ad7eff23891c3d00e27e71be18ca4184ae3ad","datavalue":{"value":"A block of a sequence is a subsequence consisting of consecutive terms of the sequence. A sequence of the form \\(s_1s_2 \\cdots s_ms_1s_2 \\cdots s_m\\) is called a repetition. A sequence is called nonrepetitive if none of its blocks is a repetition. For any set of colors \\(\\mathbf C\\), a coloring of a graph \\(G\\) is a function \\(c: V(G) \\rightarrow {\\mathbf C}\\). Let \\(B_m\\) be the collection of all repetitions of length at most \\(2m\\) over \\(\\mathbf C\\). We say that a coloring of \\(G\\) is \\(B_m\\)-free if for every path \\(v_1v_2 \\cdots v_k\\) we have \\(c(v_1)c(v_2) \\cdots c(v_k) \\notin B_m\\). Thus a \\(B_1\\)-free coloring is just a proper vertex-coloring and a \\(B_2\\)-free coloring has been studied under the name star coloring. An outstanding open problem posed by Alon et al. asks if there is a constant \\(k\\) such that every planar graph has a nonrepetitive \\(k\\)-coloring. It is proved in this paper that every outerplanar graph has a nonrepetitive 12-coloring and a graph with tree-width at most \\(t\\) has a nonrepetitive \\(4^t\\)-coloring. The authors also construct 2-degenerate graphs of girth \\(2m+2\\) which have \\(B_m\\)-free 5-colorings but no \\(B_{m+1}\\)-free \\(k\\)-colorings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$80D141B9-50BB-46B3-99C1-925D8FEF6BA2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941387$169102A5-5016-4B40-895C-2704C28D7B75","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2d82222a23c6fa5df371b8bafdd07cb623de6bc4","datavalue":{"value":"5321319","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941387$377858DD-F7A2-4673-A9D4-5357D1768585","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d502ab3afc5cccfc18f7081f2e0a3864c74ed8ef","datavalue":{"value":"repetition","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$FAA8A389-76B8-455C-806D-D2A63A41823F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac7c82d7e91b9bdaf14df44f85428c2f819b1397","datavalue":{"value":"squarefree coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$5A7C7767-91A1-42CF-95AA-DAEC24A36997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27dd40b051b95515a99e1e703a64636a11d4dfb4","datavalue":{"value":"Thue number","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$C8E7635A-996E-4E70-B816-F7930673434B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$574FA68D-29E6-4787-BC23-987F0893F15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3801589e3f1cac737b9dede93572ceb157c30bc4","datavalue":{"value":"outerplanar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$35F5F383-4BB4-4790-90F3-5D78967E0D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e763ddca700f803da0ba70e367a7e5a1bf8ceb9","datavalue":{"value":"2-degenerate graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941387$701F3BA3-965D-4E30-83A2-4D496A284582","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":"Q941387$658C7697-C92F-4E53-B5AD-90F12BDB52AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4459e1d8a1d159c65cc711f93b845d8d987553e7","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.08.043","type":"string"},"datatype":"url"},"type":"statement","id":"Q941387$B1981BE3-74A1-46B7-9685-FDA34BD3C8C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"151e262dcd101e48c297edeac06cc56cb484b00a","datavalue":{"value":"W2105469400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941387$9EB20ED3-6660-4446-B0F8-60FC58DE376A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"038d5917382c0fd149a1bb65036b953c382a3e59","datavalue":{"value":"Q30048336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941387$13D509DB-5E4C-4F3F-9A9B-390C440C8FE3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c1115e87dc51532b4feca2a675e0421662ac53","datavalue":{"value":{"entity-type":"item","numeric-id":1883636,"id":"Q1883636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$02AC6DB8-D1E8-40EA-BC1A-F1280ACCD45C","rank":"normal"},{"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":"Q941387$ECBA44A2-AB4D-4F26-9737-C2654A124B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$3A5B7B1A-8ED5-4EE5-B7AC-40211A354A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"326b85f287be07f4d8c33734ee147754f437a156","datavalue":{"value":{"entity-type":"item","numeric-id":4448754,"id":"Q4448754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$F10145E9-7E4E-4BF4-8642-03BB75F30D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"683a43415087f1adbb46b9286475847dfd19768c","datavalue":{"value":{"entity-type":"item","numeric-id":941381,"id":"Q941381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$26BCD471-93DB-4DED-ADBD-1FDAA15E525A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac40c6cf68874e578148471cf13e5477b00b1532","datavalue":{"value":{"entity-type":"item","numeric-id":5692719,"id":"Q5692719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$A6EE1191-8D1D-430E-BD8C-9CF892D3A085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$12977A02-2E56-48A8-80D9-5F6051520787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a583b336166cebbddf1ca439ee3458ed6982ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1338321,"id":"Q1338321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941387$F23D920A-37B1-4AC3-B438-E828FF5E0055","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a7f5443a5f517280ca9263a4c1364a40922c266","datavalue":{"value":"10.1016/J.DISC.2007.08.043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941387$CB9D8931-8C15-4C6C-AE95-E4177616C1C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd208bb20c83084987ed60074ff3d34415ddaa33","datavalue":{"value":{"entity-type":"item","numeric-id":4798171,"id":"Q4798171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e43a9478e10ecbb0fb0586ee8323db69d596fa8","datavalue":{"value":{"amount":"+0.8730123043060303","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":"Q941387$EB6B2AE3-A37F-4A8F-B76D-74D042071D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e71183a88fd2fdedac9732192a2193897ce87df8","datavalue":{"value":{"entity-type":"item","numeric-id":1010826,"id":"Q1010826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"500d581f3a1040a6dddc1b5563554754fdc8c9eb","datavalue":{"value":{"amount":"+0.87264084815979","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":"Q941387$126E1EC8-5B17-49B4-ABAD-9C044714845B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a297a2f8329b06dde39cb02c12b90de10e9ef953","datavalue":{"value":{"entity-type":"item","numeric-id":3576675,"id":"Q3576675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2024310a70f659d101aaa12327bea3c85e7295d","datavalue":{"value":{"amount":"+0.8715811371803284","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":"Q941387$261B49E5-F0C9-4586-8EB4-20C7F833D824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53cd2173b013e81e19a3ff582abac791a6f5803e","datavalue":{"value":{"entity-type":"item","numeric-id":925326,"id":"Q925326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3d1756daca88f6889aed79f30c595ea2c06c47e","datavalue":{"value":{"amount":"+0.8676355481147766","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":"Q941387$96352CA4-E3DA-4560-B641-8E94E3F02725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"163c0fb3249a117119543c0896789749ded3b357","datavalue":{"value":{"entity-type":"item","numeric-id":504976,"id":"Q504976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abceb4e279897b96d3ba07876384d8eb32e8e108","datavalue":{"value":{"amount":"+0.8673323392868042","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":"Q941387$844978E1-0AB3-402D-A6DC-07E068A0C671","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonrepetitive colorings of graphs of bounded tree-width","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonrepetitive_colorings_of_graphs_of_bounded_tree-width"}}}}}