{"entities":{"Q2309401":{"pageid":2320144,"ns":120,"title":"Item:Q2309401","lastrevid":53697905,"modified":"2026-01-25T14:01:55Z","type":"item","id":"Q2309401","labels":{"en":{"language":"en","value":"List \\(r\\)-dynamic coloring of sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7184107"}},"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":"Q2309401$014ED39B-2FF0-4FD0-94F8-45F96CA6CB1E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd4956765f21e47148124f997e1ec29bba5a45eb","datavalue":{"value":{"text":"List \\(r\\)-dynamic coloring of sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2309401$E67EF0CD-86EC-42BB-97FB-0771EDCB2C3D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"73f09d1289fa3f2b4dd8ffdddeafd7677b4a6782","datavalue":{"value":"1472.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309401$C4C970EE-AE94-471F-9C55-B050015D06D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c2ca19bbb7458a3ff59ad7dfa87f748eb36b1db","datavalue":{"value":{"entity-type":"item","numeric-id":369795,"id":"Q369795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$B7BECF34-E635-4F7A-897B-839E55DB6199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9329971179cd1cf38774a499cf6b46db0ee9ba5e","datavalue":{"value":{"entity-type":"item","numeric-id":328714,"id":"Q328714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$910D9470-D48B-43C4-B836-4D979D92123F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$34279529-5A1C-4719-A2DD-8C449B625629","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ae93340bb7a022b561aa0e536e029632aaf17ce","datavalue":{"value":{"time":"+2020-04-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2309401$CC1174A5-02BC-47CA-9096-9E24E8913E5D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcc7124f2fa2889c5fa92139a8279f46ec9de86a","datavalue":{"value":"An \\(r\\)-dynamic coloring of a graph \\(G\\) is a proper coloring of the vertices of \\(G\\) such that the neighbors of every vertex receive either at least \\(r\\) colors or all different colors. The \\(r\\)-dynamic chromatic number of \\(G\\), denoted \\(\\chi_r(G)\\) is the minimum number of colors required in an \\(r\\)-dynamic coloring of \\(G\\). The list \\(r\\)-dynamic chromatic number of a graph \\(G\\), denoted \\(\\operatorname{ch}_r(G)\\), is the list version of the \\(r\\)-dynamic chromatic number; in other words, each vertex has its own set of possible colors instead of a universal color set. This article proves the following three results regarding the list \\(r\\)-dynamic chromatic number of a graph \\(G\\): \\par if \\(G\\) is planar with girth at least \\(5\\), then \\(\\operatorname{ch}_r(G)\\leq r+5\\) for \\(r\\geq 15\\), \\par if mad\\((G)<\\frac{10}{3}\\), then \\(\\operatorname{ch}_r(G)\\leq r+10\\), \\par if mad\\((G)<\\frac{8}{3}\\), then \\(\\operatorname{ch}_r(G)\\leq r+1\\) for \\(r\\geq 14\\).  The proofs utilize the popular discharing method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309401$26B7625F-D3FA-40EC-82A7-41702E69B8CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d867083033b8c1726c66169322554aae1d87f519","datavalue":{"value":{"entity-type":"item","numeric-id":400410,"id":"Q400410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$C1D5BC2B-E01B-444A-A94E-9A45AC2228F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309401$1E578E4B-9123-4658-99C7-10C7E19198B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309401$B6846BB2-6CB8-4B14-AC17-3AA253886002","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"971885bb01c9f321bd1df8175ebe8cab04ca5b65","datavalue":{"value":"7184107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309401$2BA1D8ED-5B3F-4D0F-B0DF-5EC01E872654","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309401$8BFB3CAA-4799-4F60-8070-2F37D50523BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95be935caf05d156bb9cb5c9f031788955940a82","datavalue":{"value":"dynamic coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309401$8D5E2646-02B4-44A0-9BC3-374D0A6D96DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0286134cd56ebaa48cb73a6a7c2e961fe7af2df2","datavalue":{"value":"discharging","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309401$15F0C380-36DE-4A6C-87A8-90B9FF5C8831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d3fc3f306278971b47588c54be6220243123d7e","datavalue":{"value":"sparse graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309401$CE91FD8E-CC58-4E7B-BE17-E37649F573CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2309401$1400034A-4D2B-4848-BC8F-7A74560AEE63","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":"Q2309401$3A94B1B7-1CEF-4750-9692-C3E69591FA80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c35341839c932bc194f7bba362e02c316158184","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2019.05.032","type":"string"},"datatype":"url"},"type":"statement","id":"Q2309401$1E257519-E633-41B8-ADA8-A57F263D36E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7b8a865a9c5ced9e24a146e4ad8709fd417d73be","datavalue":{"value":"W2955020584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309401$904CE80E-F372-4866-9E1C-6D2CDBC1BF08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$6D03476E-8BF5-4625-8517-BB170F50084B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2802f48d595f5df6b4168e31795f85e408210317","datavalue":{"value":{"entity-type":"item","numeric-id":1928491,"id":"Q1928491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$764FA19F-94E3-4252-8A12-4735E97A1B94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211478dd61c5a17ca97122ca5b6b23b1a3480a23","datavalue":{"value":{"entity-type":"item","numeric-id":3539931,"id":"Q3539931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$C21CB5D7-F6DE-4F9D-892B-6FE4FD5FF79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"925468aa2a55be4d2f8128111e29f9b3a130aa33","datavalue":{"value":{"entity-type":"item","numeric-id":423914,"id":"Q423914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$416B2BFA-8FB5-4D81-A26B-C61C9D2DE214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8f4d7348d8acf9e956a16cb207f6e112c88013f","datavalue":{"value":{"entity-type":"item","numeric-id":1701096,"id":"Q1701096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$72561458-7A73-41E1-92D4-0C3C7E32AB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a415e76a6c4dfffab8c5043c692bae1e05da99b","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$15A50CBF-F885-4131-9BAE-1CA856C3FA08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d63eeb49b8e30656ce256f9c15b39020142c37f","datavalue":{"value":{"entity-type":"item","numeric-id":277619,"id":"Q277619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$84771C67-4CEE-4F16-8035-3A991D831DAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9706496416c2b1beef2d8c4cc8b03c0bf1facbcc","datavalue":{"value":{"entity-type":"item","numeric-id":2446867,"id":"Q2446867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$FAE59BCF-356E-4D20-9FDF-1A1067CF43BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7799d1e67e85b76392661762a1661535e2f3259","datavalue":{"value":{"entity-type":"item","numeric-id":5199147,"id":"Q5199147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$2E9316C9-36D1-4B37-8C27-9AC864C40BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31f4df5bb481048b1705d78febd3696d134a581b","datavalue":{"value":{"entity-type":"item","numeric-id":1709543,"id":"Q1709543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$514044A9-4D4B-49FB-BA0C-3EF183E8D04E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44356ed4a971b2a7a1f3a153064861528dabdf00","datavalue":{"value":{"entity-type":"item","numeric-id":2501581,"id":"Q2501581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$9A2B14E2-40A2-4744-8BF3-25E3A60A62FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d924c1ba586e60f4cb67e3af2692245723c5420","datavalue":{"value":{"entity-type":"item","numeric-id":5466088,"id":"Q5466088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$95E39C27-A800-4666-A698-2CDB17DBFB0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b900a90b4fc6aaeedc28443595635fd607853c74","datavalue":{"value":{"entity-type":"item","numeric-id":1786882,"id":"Q1786882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$0935F4F6-20E7-4AD2-B7BA-E550165024F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee6d69698dc59784d0fa30f4088469efc871c092","datavalue":{"value":{"entity-type":"item","numeric-id":1682887,"id":"Q1682887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$666D9876-BE7A-47D8-9C0C-25E4972B26B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6e0627601eb678357cd6a182e4c3a611cabaca","datavalue":{"value":{"entity-type":"item","numeric-id":1182897,"id":"Q1182897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$00DDEAC2-A16F-467E-8937-2C99342BD7F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61275c67909e8cee67acbd8aaa57255f1a82ffcb","datavalue":{"value":{"entity-type":"item","numeric-id":393165,"id":"Q393165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$D142CFF8-16DD-4D08-8B6D-9C6B976B45EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"331d28f91553035d395fc2bf9ac39006e56fb89d","datavalue":{"value":{"entity-type":"item","numeric-id":1752467,"id":"Q1752467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$BE6B42D7-33A9-4540-BE24-8DD583E9F626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e664b99c761413e30942462f0c6c1a21b43f6479","datavalue":{"value":{"entity-type":"item","numeric-id":897613,"id":"Q897613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$16EEB6A0-1065-4F97-B3F0-FC51C5798C67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89c130c5255d40289ff7fb6b3df3ed44923b00aa","datavalue":{"value":{"entity-type":"item","numeric-id":2424825,"id":"Q2424825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$9A4C4884-F5F1-417E-B97E-AB20AED0A6EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a8e77b4c87707accaae64f14a6485580276d8e4","datavalue":{"value":{"entity-type":"item","numeric-id":1680495,"id":"Q1680495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$DAD3696D-7082-40CF-95FA-CE6C6E1FBE64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b80336090668681bc6bd30fec89524426e798b8a","datavalue":{"value":{"entity-type":"item","numeric-id":1732119,"id":"Q1732119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2309401$13AEA621-8C5B-473D-9201-172CBE3DD39A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2faea9f945515066fd7287d357f153d7a8b44364","datavalue":{"value":"10.1016/J.TCS.2019.05.032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2309401$6BAE7040-42A3-440C-817B-3F1E8AE6410B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"316852e7e22a330704cfec92b7e340a4be9aea4a","datavalue":{"value":{"entity-type":"item","numeric-id":1732119,"id":"Q1732119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417c92dd962def0ffd4a9e19ecad4c00feffb52f","datavalue":{"value":{"amount":"+0.918397068977356","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":"Q2309401$7991F277-2DC0-43E4-A567-D823892AAFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7c4bb0feef6829e631ad9805c5afb1fbaee4a2c","datavalue":{"value":{"entity-type":"item","numeric-id":2424825,"id":"Q2424825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2920e44df1497cc0cf57577c9d3a1e6383742fc","datavalue":{"value":{"amount":"+0.9045477509498596","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":"Q2309401$D581830C-75D5-4C5C-A6A8-FA0CA9B32332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a0d421bc57fd03063efaa55bba8c595f976cf8c","datavalue":{"value":{"entity-type":"item","numeric-id":5199147,"id":"Q5199147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d50aa284deee8fe5f41b2c0e1b3df8b2b6756b26","datavalue":{"value":{"amount":"+0.902093231678009","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":"Q2309401$7B397F0F-B359-4422-8B63-6CB815F14C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01d840c697c67ab74988d6b0753f9b916f3c8227","datavalue":{"value":{"entity-type":"item","numeric-id":6049080,"id":"Q6049080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bc94043446dbf3e41ae10bab618556e46992e22","datavalue":{"value":{"amount":"+0.8982682228088379","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":"Q2309401$D0A0CBF9-D74E-46B0-9487-B44A5919A9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc0806a681eaedc1a039bf7169a5f1c614fa333d","datavalue":{"value":{"entity-type":"item","numeric-id":1709543,"id":"Q1709543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6448d49e01eb356b914848dc1e2c6a60078be41b","datavalue":{"value":{"amount":"+0.8657816648483276","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":"Q2309401$202E51BC-B686-46FF-B060-98A24DB0937C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2309401","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2309401"}}}}}