{"entities":{"Q504976":{"pageid":506743,"ns":120,"title":"Item:Q504976","lastrevid":57012390,"modified":"2026-03-25T15:41:48Z","type":"item","id":"Q504976","labels":{"en":{"language":"en","value":"Pathwidth and nonrepetitive list coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6675975"}},"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":"Q504976$383F1205-FC35-45F1-8F88-C46AE13686FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4a83801a43fff9656a25b5e9c0cf5a936145c8d","datavalue":{"value":{"text":"Pathwidth and nonrepetitive list coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q504976$050F774F-CC4D-4D78-AAB1-DF206C6A3936","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"364a15da2255b5c4d3fca0b2c658a7dcde343cf1","datavalue":{"value":"1353.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q504976$08DA815A-44BD-4B21-B7D2-B928C441546E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"971461748f5aee02f8ad691e9ead14422343074f","datavalue":{"value":{"entity-type":"item","numeric-id":504975,"id":"Q504975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$839A7663-C031-4666-8282-A47B2CB02F0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb1d48e699dcbd07426b1c3ee3831813e5c5d7b0","datavalue":{"value":{"entity-type":"item","numeric-id":412238,"id":"Q412238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$D314814A-8BBC-47C7-BCFE-65D9C2A1A3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc629f0be60f72a336737629e351e85a1cdd011c","datavalue":{"value":{"entity-type":"item","numeric-id":322291,"id":"Q322291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$CA6B8002-D689-4602-B203-AE10BEEBC870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4cd896cc324ed8d238532cc31bb366d571b9dcae","datavalue":{"value":{"entity-type":"item","numeric-id":377498,"id":"Q377498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$437C160A-FBF5-44DB-B900-0E726A4DEF26","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":"Q504976$E7DD95C0-DA0B-4C9F-8528-DAD77840D99C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"da62c406b4a04eca20d16dbf434fddd11a83f858","datavalue":{"value":{"time":"+2017-01-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q504976$2B9DE66A-CA9A-48AB-B0E9-D406281DBD7D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bf599b6f7f34d5340f023d4caeeeb8724735163e","datavalue":{"value":"https://arxiv.org/abs/1601.01886","type":"string"},"datatype":"url"},"type":"statement","id":"Q504976$5A6E6A72-DE50-47C7-9DA6-7F813F56D4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"64f90381644585796c5cf4b9bb327d3d08345912","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p40","type":"string"},"datatype":"url"},"type":"statement","id":"Q504976$DDFC510E-C667-4184-AB40-7F6A09CE752E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"60222d8ff4232dafaa8ec15e266d3f44b4227086","datavalue":{"value":"Summary: A vertex coloring of a graph is nonrepetitive if there is no path in the~graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), \\textit{F. Fiorenzi} et al. [Discrete Appl. Math. 159, No. 17, 2045--2049 (2011; Zbl 1239.05064)] recently showed that this does not extend to the list version of the problem, that is, for every \\(\\ell \\geq 1\\) there is a tree that is not nonrepetitively \\(\\ell\\)-choosable. In this paper we prove the following positive result, which complements the result of Fiorenzi et al. [loc. cit.]: There exists a function \\(f\\) such that every tree of pathwidth \\(k\\) is nonrepetitively \\(f(k)\\)-choosable. We also show that such a property is specific to trees by constructing a family of pathwidth-2 graphs that are not nonrepetitively \\(\\ell\\)-choosable for any fixed \\(\\ell\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q504976$C4A944AB-C821-4A0C-B142-B793C93F53C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q504976$24F7413C-B4F5-445C-8B43-2E3A240A44F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a911b181ef250786dab4b6b29e50008104874201","datavalue":{"value":"6675975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q504976$1C55420D-44BC-416E-A9E9-95741A17F998","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q504976$E6D0AC1E-6424-4E57-AA69-F1651E012F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e3ce293966f0b0fa9cebc2e6529d0a40e222ad","datavalue":{"value":"nonrepetitive coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q504976$FB41DA65-051D-4CC8-89E9-68760110FDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67f458d393b772a7cf36a53976d2b5be911e683d","datavalue":{"value":"pathwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q504976$128278E6-ABDE-4B12-A810-AFB1A4ECD003","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":"Q504976$6A647760-C97F-4DB1-9FC2-66221539B472","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":"Q504976$420C3864-D974-4223-B84E-5FD510287D43","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":"Q504976$C0B9CC66-7978-42E9-B366-3A6EDCEA4FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$21DB8002-9A65-4B8A-8F34-32621883F044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2d54796c1164ac521f218989b7237fe872e8f12","datavalue":{"value":{"entity-type":"item","numeric-id":1953438,"id":"Q1953438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$11C70914-4550-43B0-8A5B-51F248DBF071","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":"Q504976$18724108-AA08-4D16-9728-5370D739092E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70dbd7b39999ea93f240ee30d244f82a2552144e","datavalue":{"value":{"entity-type":"item","numeric-id":411845,"id":"Q411845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$A534CE88-660C-4890-AC95-8E522D3FF501","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":"Q504976$2DE11313-9FA8-4E02-8BB9-A33400DDC319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35912017dd6aa8092ff0d53f45f1ad24825db48c","datavalue":{"value":{"entity-type":"item","numeric-id":878624,"id":"Q878624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$73E57F66-D338-4FB0-AD70-7A437F5A9C58","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":"Q504976$AADE5B9F-413A-4D22-B284-316931F194EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42b068503fa4c91041d7e08bdbea8a275aeb3d95","datavalue":{"value":{"entity-type":"item","numeric-id":3068765,"id":"Q3068765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$BD94FF6F-100D-4E8A-8F9F-ADFD5E2A4C76","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":"Q504976$3B4277DE-5A0F-4F42-970C-8E6739D216A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"665379fb5a21b68f392dabab6b2534854e3f53a7","datavalue":{"value":{"entity-type":"item","numeric-id":5300504,"id":"Q5300504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$C29638CA-D34C-4A2A-A38F-3AD08AB50A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff51f4b236b91a98d0219658330b8b313a8992c3","datavalue":{"value":{"entity-type":"item","numeric-id":941387,"id":"Q941387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$F130A5AC-D3D9-406F-988C-249D56E9ED46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d06f971812093fe6317243e078dd346e71338f6","datavalue":{"value":{"entity-type":"item","numeric-id":3578191,"id":"Q3578191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q504976$EF8F9FCA-4607-4DBA-9BD9-77D95E46471E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"382e9b94d3b919f82ec111b1edf834694900ef95","datavalue":{"value":"bafkreid3ugpxo2i7eqlxarouov2us74ydffxr6fqcift7ga6xl3y26ssyi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q504976$C683E47E-EF25-4164-A196-F74567E11E9D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed0a43684fd077683a610597c37b7adf3b2d6fd7","datavalue":{"value":{"entity-type":"item","numeric-id":5300504,"id":"Q5300504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fcd93b6a55485b646cf108266404935924b9320","datavalue":{"value":{"amount":"+0.8855973482131958","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":"Q504976$581AB812-0600-40F4-AF9A-83A2EE8B1C45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38bb9ade2f84bab5e399a29238e10fe0af12d742","datavalue":{"value":{"entity-type":"item","numeric-id":941387,"id":"Q941387"},"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":"Q504976$FD40FB6E-33D2-4C1F-BF82-256D96437DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bf1fd08e05e2f13ab3ca0fb8a5be1a9e7f6e1ae","datavalue":{"value":{"entity-type":"item","numeric-id":864157,"id":"Q864157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a489ab0ea1b5db5ac7b1cffd622b754b917d3313","datavalue":{"value":{"amount":"+0.8598828315734863","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":"Q504976$A44A2A01-4C91-4F4C-BFCC-11B996B2D824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5300f3cc5462287796974f3d07cfcde55c4c2de","datavalue":{"value":{"entity-type":"item","numeric-id":3068765,"id":"Q3068765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35ea2f00cfbfbbab6d13508788251fd5cf76fee2","datavalue":{"value":{"amount":"+0.8447829484939575","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":"Q504976$1EB5421C-10FD-4A47-AA57-37D09138E7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfeed2f4949a7b12b076a1f36700fecb6ed49507","datavalue":{"value":{"entity-type":"item","numeric-id":411845,"id":"Q411845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c248c0add71daa9c7eeaad479c8e09f64e24d26","datavalue":{"value":{"amount":"+0.8388924598693848","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":"Q504976$CBA74733-E9A5-4609-A51A-F069F270C757","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:504976","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:504976"}}}}}