{"entities":{"Q2195220":{"pageid":2205963,"ns":120,"title":"Item:Q2195220","lastrevid":57775491,"modified":"2026-04-02T11:48:53Z","type":"item","id":"Q2195220","labels":{"en":{"language":"en","value":"Another approach to non-repetitive colorings of graphs of bounded degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7244781"}},"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":"Q2195220$4B2623F1-BDE8-48EE-B5AC-4408BD939DA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"74cab8856d2314691751de8c8fb4dd6bc1eec1f8","datavalue":{"value":{"text":"Another approach to non-repetitive colorings of graphs of bounded degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2195220$D6C6DCB4-EE9F-47FB-B5CF-BCC4ACE4C7F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"10fbf0167c7625af57fe020a132a2760c15c91c5","datavalue":{"value":"1441.05083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2195220$21A91C98-DAB9-4C21-A515-5AED6031C3C7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"17d33f8c5256f73055fb60a40188c3debfbfa4ae","datavalue":{"value":"10.37236/9667","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2195220$C30594CA-24B4-4602-997F-49A346C6CE7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"78345249e55a9bb9c4e6d502130671e58eccc6b9","datavalue":{"value":{"entity-type":"item","numeric-id":668060,"id":"Q668060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$155C30EA-DDA3-4187-8951-4A04A5DF975C","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":"Q2195220$95E14C00-C93A-4E78-831D-684A2BD6552C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0c27025de8b388440ce9f14f6354e419dbcdb6a4","datavalue":{"value":{"time":"+2020-09-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2195220$B6F7469C-9355-48B0-A26D-EF9E90FB9601","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ad5578cfa57cb9dbe3d5f15d201f717b5f05751f","datavalue":{"value":"https://arxiv.org/abs/2006.09094","type":"string"},"datatype":"url"},"type":"statement","id":"Q2195220$24898DE9-BA97-4F33-BCA6-FD7167F838C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1b4e121355ade8943c372195d6b28824ccd0d239","datavalue":{"value":"Summary: We propose a new proof technique that applies to the same problems as the Lov\u00e1sz Local Lemma or the entropy-compression method. We present this approach in the context of non-repetitive colorings and we use it to improve upper-bounds relating different non-repetitive chromatic numbers to the maximal degree of a graph. It seems that there should be other interesting applications of the presented approach.  In terms of upper-bounds our approach seems to be as strong as entropy-compression, but the proofs are more elementary and shorter. The applications we provide in this paper are upper bounds for graphs of maximal degree at most \\(\\Delta \\): a minor improvement on the upper-bound of the non-repetitive chromatic number, a \\(4.25\\Delta +o(\\Delta)\\) upper-bound on the weak total non-repetitive chromatic number, and a \\(\\Delta^2+\\frac{3}{2^{1/3}}\\Delta^{5/3}+ o(\\Delta^{5/3})\\) upper-bound on the total non-repetitive chromatic number of graphs. This last result implies the same upper-bound for the non-repetitive chromatic index of graphs, which improves the best known bound.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2195220$72F807BE-847D-43C8-95AA-5EA13E5689DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2195220$3F29C759-AF62-424F-8408-83E2E9FD7794","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b93a736b1ee26bdfb8d72bbc3c4315d7e36c1f44","datavalue":{"value":"7244781","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2195220$9A982D35-3C36-4444-92BD-B43AC6135925","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":"Q2195220$9A12682B-7433-4AB6-959A-7D39198C7F14","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d34ad3cf996354821364cbe20be2bcef37d427f5","datavalue":{"value":"W3083052155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2195220$4BB6B5D1-04B1-4A23-AE23-695480134818","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":"Q2195220$D67C7404-8952-4633-84AF-AA64D598015C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95fa878fb2c02613b94617992debe081ca5a953e","datavalue":{"value":{"entity-type":"item","numeric-id":2381499,"id":"Q2381499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$C6314AC1-33E2-435B-A994-F630A654310C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37a65cac845b5c813e1e0ea435ee7e09d8d2f8fc","datavalue":{"value":{"entity-type":"item","numeric-id":2357223,"id":"Q2357223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$50C9993A-C6E3-4ABA-BDE4-E2B4C9C91E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b059d98e87e125a4ec7586a7e05320642b9ba1b","datavalue":{"value":{"entity-type":"item","numeric-id":393106,"id":"Q393106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$1B0D6F66-C8C2-4E0F-85FC-EFEB782D7330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf7f335dd4e3a6b6c7263f02d1edfb4ec68bb0a6","datavalue":{"value":{"entity-type":"item","numeric-id":5899395,"id":"Q5899395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$F46A6256-A27B-4C57-BC6A-3A7868911F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c131457ad802f87615221ca6e34b95944d1d4cf","datavalue":{"value":{"entity-type":"item","numeric-id":5126756,"id":"Q5126756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$0EE74492-54A9-4E78-9007-7B4068813A84","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":"Q2195220$AAB5822D-D9B8-4DCF-81D6-30A381837050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbba895f8d0ef9e7d508881c55e2503f08f206db","datavalue":{"value":{"entity-type":"item","numeric-id":2444732,"id":"Q2444732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$6E0E357F-F254-4FF0-AB3F-0EF5CF7CDB11","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":"Q2195220$156EE2D4-0548-4482-A2B9-59E3FD07B068","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":"Q2195220$CF850A82-A1B0-4680-BB0F-4C3040A39250","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":"Q2195220$CC48AD33-1C4B-49A7-8EBF-EE8B2505EEB0","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":"Q2195220$B1459671-CAE3-41BC-AAD4-B1D1AD3A8FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"756dee485802f0d87b220bea0f3b7679f8925171","datavalue":{"value":{"entity-type":"item","numeric-id":2635083,"id":"Q2635083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$F4F8B98B-D338-4975-80A6-9CA3AA0C3CB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40afc6d6cf261b10a183c431434c5d0190bb4924","datavalue":{"value":{"entity-type":"item","numeric-id":547794,"id":"Q547794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$44572CDC-60B9-487B-AA3E-D61DCD5B8D42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a3b63471ca7676abec6499e6f8e070eaebf45bf","datavalue":{"value":{"entity-type":"item","numeric-id":2340970,"id":"Q2340970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$1A812501-36FE-43C4-A628-49DD08C44DCC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"45fa8750800fda02e48a1ed9173fc0c07179205e","datavalue":{"value":"bafkreicr7hw2nl7wje5ast7hiozioga5ujingbww5uanqlisodvzl74kb4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2195220$7A3F1F4F-C64B-437A-8033-A064D7C4FAA0","rank":"normal"}],"P1643":[{"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":"3418b0ae15874232fe5ebf3464eec270653dae2e","datavalue":{"value":{"amount":"+0.9202199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$33A0CFB9-E032-4F61-87FB-78EC972DC6A5","rank":"normal"},{"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":"3418b0ae15874232fe5ebf3464eec270653dae2e","datavalue":{"value":{"amount":"+0.9202199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$9A3DC8DD-8AC8-4DAF-83DF-4C7443DEE4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"808752467001500aac7ed66c91be9e52bab891e9","datavalue":{"value":{"entity-type":"item","numeric-id":5899395,"id":"Q5899395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3418b0ae15874232fe5ebf3464eec270653dae2e","datavalue":{"value":{"amount":"+0.9202199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$4CD2F0AB-81E8-426C-8A60-4045B5F75EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae380398d2bd657c4095f7995e7d4c9576b39669","datavalue":{"value":{"entity-type":"item","numeric-id":5899374,"id":"Q5899374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3418b0ae15874232fe5ebf3464eec270653dae2e","datavalue":{"value":{"amount":"+0.9202199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$735F9B34-2541-43D6-B8ED-F252AF6DC817","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":"f6f82312961d53ef8942f2cb15cb8d839b73e839","datavalue":{"value":{"amount":"+0.9168094","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$21FC3898-6F4B-4283-8E0A-84A74656F963","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":"665281a703ad677f6da179cee9bf2f7233fa51ad","datavalue":{"value":{"amount":"+0.9155626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$AC1A658A-C940-45A2-B76D-BF0F26201539","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":"564d8c0da1538f6157934335fbfa27f6b0006eb5","datavalue":{"value":{"amount":"+0.9110326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$349C9E4C-7A24-44DF-B578-341BCBDCE726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64bab209dc2437f08b6f1cc9df5d6586efbc4f36","datavalue":{"value":{"entity-type":"item","numeric-id":4852403,"id":"Q4852403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfe8d77d34e185950a3997a85a1c45d8062bfe69","datavalue":{"value":{"amount":"+0.91057026","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$26A5692B-A97F-475E-ABCF-A6E2606EFA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29a05078f1357e552b72a091ec453b069f685c21","datavalue":{"value":{"entity-type":"item","numeric-id":658062,"id":"Q658062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eb6fb6e2f0697b73cb094ad31ab3107f98f3dd8","datavalue":{"value":{"amount":"+0.90998304","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$A6E773BB-F1CE-44C0-B8CE-7902148EBD32","rank":"normal"},{"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":"452aa7d87a5e55b49a98a99c387f880f7d32369c","datavalue":{"value":{"amount":"+0.9043917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2195220$F79504E1-26B6-46A0-9BC4-1B54F842442F","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2195220$6CF68F97-20EB-4F19-8693-8D3D9A8ED5E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2195220","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2195220"}}}}}