{"entities":{"Q1010826":{"pageid":1012674,"ns":120,"title":"Item:Q1010826","lastrevid":66595179,"modified":"2026-04-12T11:11:09Z","type":"item","id":"Q1010826","labels":{"en":{"language":"en","value":"Notes on nonrepetitive graph colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541004"}},"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":"Q1010826$DBAAD4E3-62CF-4CD1-A7C9-24DC2263FC35","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d03e2013c16bda9b6dd1f5aa76f34fb13b2428b","datavalue":{"value":{"text":"Notes on nonrepetitive graph colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010826$ED13D0C7-D872-4053-907B-0B5F8A65F754","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f144ddb9bccb5a992b77c49e4edb5a396898b5a5","datavalue":{"value":"1163.05316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010826$5170F89E-B352-4366-A0E4-51F6EBBB4245","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"128ea2f3fc3f9dd84635387102467d325ee845b5","datavalue":{"value":{"entity-type":"item","numeric-id":215792,"id":"Q215792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010826$448F88E6-5C22-4722-A455-C48F20812EE7","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":"Q1010826$4CE7F89E-5045-4D0B-89E6-B5740822113E","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":"Q1010826$53BB6F10-43B4-4F2F-8A9F-DCD53952EE40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010826$E7566F5E-FD34-41D5-9062-881E69A1C566","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dded445ff81b825b050cde6d0d4c792a8cde24f6","datavalue":{"value":"https://arxiv.org/abs/math/0509608","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010826$31732C98-37F0-4D41-AD8C-1C40CE4793B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"cf627ed73564ea4ec00bf49a0cc5cdea8319fc40","datavalue":{"value":"https://eudml.org/doc/129978","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010826$024C3C03-F279-4FF0-AF45-E200106639C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd720c739ce9a7a95ac661b704e91d28ff3dc218","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r99.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010826$B2EF5674-6668-4F44-8C14-70617D0F66DD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"457fcaf360a33cd77f908c1375c53ec8cc76e8ff","datavalue":{"value":"Summary: A vertex colouring of a graph is nonrepetitive on paths if there is no path \\(v_1,v_2,\\dots,v_{2t}\\) such that \\(v_i\\) and \\(v_{t+i}\\) receive the same colour for all \\(i=1,2,\\dots,t\\). We determine the maximum density of a graph that admits a \\(k\\)-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree \\(\\Delta\\) has a \\(f(\\Delta)\\)-colouring that is nonrepetitive on walks. We prove that every graph with treewidth \\(k\\) and maximum degree \\(\\Delta\\) has a \\(O(k\\Delta)\\)-colouring that is nonrepetitive on paths, and a \\(O(k\\Delta^3)\\)-colouring that is nonrepetitive on walks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010826$66037C6E-19A2-4DC9-8B5B-426E4E8FE0F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010826$ACFB40EA-DDF6-48CA-BB8E-BFDC60EEB470","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de7ffa9b8f4fa8d387ad21064eadef42b1c6c81b","datavalue":{"value":"5541004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010826$D4676E04-BC96-4424-8550-028B43AEF723","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":"Q1010826$316435FC-4901-4AAF-8F59-80CEE4150A4C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"409bc84fb7609497b4d5e09f71ae6b040cf24bc8","datavalue":{"value":"bafkreidx4hxwlfmhseacam352cxgw6pwwbrcfm34xto5f3rafjgxh7rkua","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010826$15506D8F-8FCC-4782-A10B-8198710D2FA2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a8c0af4b801a42347f0eabed3d77277453a756d","datavalue":{"value":{"entity-type":"item","numeric-id":2122918,"id":"Q2122918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c816469e485ff6ed5f1661564a17812ac99f06b4","datavalue":{"value":{"amount":"+0.8805409669876099","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":"Q1010826$E87E5C62-BE49-454C-8BCC-7DC821677F92","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":"50718c976bd5779e54143066fe6155f298a8b7e3","datavalue":{"value":{"amount":"+0.8771281242370605","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":"Q1010826$9336169C-9649-4AF4-89D7-D706F85D7CFF","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":"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":"Q1010826$0F86CEB0-572A-4490-84CB-5A2530A783C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aed516c76bbeb59828666ebee47e9e731edca632","datavalue":{"value":{"entity-type":"item","numeric-id":524188,"id":"Q524188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c75d628a508a5a3bd64b70e114cf5be9e67189c","datavalue":{"value":{"amount":"+0.8706207275390625","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":"Q1010826$9A01F99F-DFD9-4A29-BAAC-66A312AAC503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d38e1aa8a20978aca9db3de76435608e4ce67476","datavalue":{"value":{"entity-type":"item","numeric-id":1953438,"id":"Q1953438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b18ece8b344afdee5217f1125e5d023d676028f","datavalue":{"value":{"amount":"+0.8656418919563293","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":"Q1010826$60287F41-DBF3-4D25-B0C0-5E2A0A5FB84F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Notes on nonrepetitive graph colouring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Notes_on_nonrepetitive_graph_colouring"}}}}}